Wednesday, March 26, 2014

Dijkstra's algorithm for single source shortest path is a greedy algorithm. Here we find the shortest path from a single source in a weighted say directed edge graph where the weights are positive. In the undirected graph, there are two directed edges replaced by a single edge. There could be multiple paths with different weights but the shortest path is one with the smallest weight. To find the shortest oath, we relax the edges that is we take the minimum cost of the edge joining two vertices u and v and set that ad the edge weight. If the shortest path consists of edges v1, v2, v3....vn, any contiguous subset if these is also a shortest path. We now look at the possibility of a shorter path.
Each new shortest path extends an earlier one. So we build the shortest path in the ascending order of costs. When we add a vertex, we see the cost. If there are no edges to that vertex the cost is infinity.
In the algorithm We first initialize the costs.  When we pick a source vertex we do tge following for each of the other vertices.
We choise a vertex u that is not already in the set and has a minimum cost. Then we mark it as included in the shortest path.  For each of the neighbors of u, we determine the cost from the set s and with the edge u to w and then relax the edge by picking the minimum costs between vertices.
In this way we include all vertices one by one in ascending order of weights 

No comments:

Post a Comment