The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph. The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex v.

Dijkstra's Algorithm

Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

• Set all vertices distances = infinity except for the source vertex, set the source distance= 0

• Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.

• Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).

• Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex with the new distance to the priority queue.

• If the popped vertex is visited before, just continue without using it.

• Apply the same algorithm again until the priority queue is empty.

Time Complexity of Dijkstra's Algorithm is O(V2) but with min-priority queue it drops down to O(V+ElogV).

However, if we have to find the shortest path between all pairs of vertices, both of the above methods would be expensive in terms of time. Discussed below is another alogorithm designed for this case.

Many more problems than you might at first think can be cast as shortest path problems, making Dijkstra’s algorithm a powerful and general tool.

For example:

• Dijkstra’s algorithm is applied to automatically find directions between physical locations, such as driving directions on websites like MapQuest or Google Maps.

Formal Description

The algorithm characterizes each node by its state The state of a node consists of two features: distance value and status label

• Distance value of a node is a scalar representing an estimate of the its distance from node s.

• Status label is an attribute specifying whether the distance value of a node is equal to the shortest distance to node s or not.

• The status label of a node is Permanent if its distance value is equal

Greedy Method Approach Page | 4

to the shortest distance from node s

• Otherwise, the status label of a node is Temporary The algorithm maintains and step-by-step updates the states of the nodes At each step one node is designated as current

Algorithm Steps

Step 1. Initialization

• Assign the zero distance value to node s, and label it as Permanent. [The state of node s is (0, p).]

• Assign to every node a distance value of 1 and label them as Temporary. [The state of every other node is (1, t).]

• Designate the node s as the current node

Step 2. Distance Value Update and Current Node Designation Update Let i be the index of the current node.

(1) Find the set J of nodes with temporary labels that can be reached from the current node i by a link (i, j). Update the distance values of these nodes.

• For each j 2 J, the distance value dj of node j is updated as follows new dj = min{dj, di +cij} where cij is the cost of link (i, j), as given in the network problem.

(2) Determine a node j that has the smallest distance value dj among all nodes j 2 J, find j_ such that min j2J ,dj = dj_

(3) Change the label of node j_ to permanent and designate this node as the current node.

Step 3. Termination Criterion

If all nodes that can be reached from node s have been permanently labeled, then stop - we are done. If we cannot reach any temporary labeled node from the current node, then all the temporary labels become permanent - we are done. Otherwise, go to Step 2.

Dijkstra’s Algorithm: Example

We want to find the shortest path from node 1 to all other nodes using Dijkstra’s algorithm. Initialization - Step 1

• Node 1 is designated as the current node

• The state of node 1 is (0, p)

• Every other node has state (1, t)

Step 2

• Nodes 2, 3,and 6 can be reached from the current node 1

• Update distance values for these nodes

d2 = min{1, 0+7} = 7

d3 = min{1, 0+9} = 9

d6 = min{1, 0+14} = 14

• Now, among the nodes 2, 3, and 6, node 2 has the smallest distance value

• The status label of node 2 changes to permanent, so its state is (7, p), while the status of 3 and 6 remains temporary

• Node 2 becomes the current node

Step 3

Graph at the end of Step 2 We are not done, not all nodes have been reached from node 1, so we perform another iteration (back to Step 2)

Another Implementation of Step 2

• Nodes 3 and 4 can be reached from the current node 2

• Update distance values for these nodes

d3 = min{9, 7+10} = 9

d6 = min{1, 7+15} = 22

• Now, between the nodes 3 and 4 node 3 has the smallest distance value

• The status label of node 3 changes to permanent, while the status of 6 remains temporary

• Node 3 becomes the current node We are not done (Step 3 fails), so we perform another Step 2

Another Step 2

• Node 5 can be reached from the current node 6

• Update distance value for node 5 d5 = min{1, 11+9} = 20

• Now, node 5 is the only candidate, so its status changes to permanent

• Node 5 becomes the current node From node 5 we cannot reach any other node. Hence, node 4 gets permanently labeled and we are done.

Dijkstra’s algorithm solves the single-source shortest-paths problem on a directed weighted graph G = (V, E), where all the edges are non-negative (i.e., w(u, v) ≥ 0 for each edge (u, v) Є E).

In the following algorithm, we will use one function Extract-Min(), which extracts the node with the smallest key.

Algorithm: Dijkstra’s-Algorithm (G, w, s)

for each vertex v Є G.V

v.d := ∞

v.∏ := NIL

s.d := 0

S := Ф

Q := G.V

while Q ≠ Ф

u := Extract-Min (Q)

S := S U {u}

for each vertex v Є G.adj[u]

if v.d > u.d + w(u, v)

v.d := u.d + w(u, v)

v.∏ := u