Lost in Compilation

Here's  Part 1  and  Part 2 And now for the third and final part of the tutorial. We'll be implementing the actual algorithm here. But before we get started, let's go over some theory. Dijkstra's Shortest Path Algorithm, (V - Number of Vertices, E - Number of Edges) Applies to both Directed graph and Undirected graphs. Greedy Algorithm. Always picks the local minimum to extend it's solution. Uses Dynamic Programming. Stores solutions from source to every other vertex on the shortest path to the destination. Edges cannot be negative. Original Implementation by Dijkstra was O(V 2 ) since it did not use a Minimum Priority Queue. Tarjan & Fredman introduced the modern version of the algorithm using a Fibonacci Heap to pick the vertex closest to the source. The Complexity thus became O(E + V logV).  Using a Binary Heap instead of a Fibonacci Heap increases the complexity to  O( (E+V) log V). Variations. There are two variants of the algorithm, t...

For Part 2 of the series, we'll be developing a Priority Queue implemented using a Heap  . Continuing from Part 1 , we'll be using Python for the implementation. Fortunately, Python has a PriorityQueue class in the `queue` module. It's more than enough for our purposes, but the Queue module was designed thread safe, so there is a small overhead that comes with it. The Priority Queue is a Minimum Priority Queue by default, it takes in tuples which are compared together to determine their position in the queue. For those unfamiliar with tuple comparison in Python, it works something like this. >>> (1,2) < (3,4) True >>> (1,2) < (1,3) True >>> (1,2) < (1,1) False >>> (1,2) < (1,2,3) True >>> (1,2,3,4) < (1,2,3) False The first non equal element  of the both tuples determine the output of the comparison operation. So say you have a bunch of Tasks Ti with Priorities Pi, then we push (Pi, Ti) into the...

This will be a 3 Part series of posts where I will be implementing the Dijkstra's Shortest Path algorithm in Python. The three parts will be 1) Representing the Graph 2) Priority Queue 3) The Algorithm To represent a graph we'll be using an  Adjacency List . Another alternative is using an Adjacency Matrix, but for a sparse graph an Adjacency List is more efficient. Adjacency List An Adjacency List is usually represented as a HashTable (or an Array) where an entry at `u` contains a Linked List. The Linked List contains `v` and optionally another parameter `w`. Here `u` and `v` are node(or vertex) labels and `w` is the weight of the edge. By Traversing the linked list we obtain the immediate neighbours of `u`. Visually, it looks like this. For implementing this in Python, we'll be using the dict()  for the main HashTable. For the Linked List we can use a list of 2 sized tuples (v,w).  Sidenote: Instead of a list of tuples, you can use a dict(), ...