### Dijkstra's Algorithm

Given a weighted graph G and a pair of vertices (s and d), the shortest path problem seeks to find a path from s to d in this graph such that the sum of the weights of the edges along this path is minimized. One famous algorithm for this problem is Dijkstra's Algorithm, which not only finds the shortest path from an origin (s) to a destination (d), but finds the shortest path from (s) to all other vertices (v) in the graph G. The algorithm proceeds as follows:

Dijkstra's Algorithm

• Initially we have an empty path tree T, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. w(v) = infinity for all v in V.
• Add the node s to the tree, and give the associated path cost a value of zero, i.e. w(s) = 0.
• Find the edge which is adjacent to T that adds the vertex whose cost is minimum, i.e. we look for an e = (u, v) such that u is in T, and v is not in T and w(u) + cost(u, v) < w(v) is minimum. If no such edge exists go to 5.
• Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex v. Go to 3.
• The path tree T now represents the shortest path from the vertex s to all other vertices reachable in the graph G. The weight vector w represents the costs of these paths. 0

Show Work?
your browser does not support the canvas tag