dijkstra algorithm.
WAP in C/C++ to find the shortest route using dijkstra algorithm.
THEORY & CONCEPT-:
The shortest pathbetween two nodes of a graph is a sequence of connected nodes so that the sum of the edges that inter-connect them is minimal.
Take this graph,
There are several paths between A and E:
Path 1
Path 2
Path 3
Path 4
Path 1
: A -> B -> E 20Path 2
: A -> D -> E 25Path 3
: A -> B -> D -> E 35Path 4
: A -> D -> B -> E 20There are several things to notice here:
1. There can be more then one route between two nodes
2. The number of nodes in the route isn’t important (Path 4 has 4 nodes but is shorter than Path 2, which has 3 nodes)
3. There can be more than one path of minimal length
Something else that should be obvious from the graph is that any path worth considering is simple. That is, you only go through each node once.
Unfortunately, this is not always the case. The problem appears when you allow negative weight edges. This isn’t by itself bad. But if a loop of negative weight appears, then there is no shortest path. Look at this example:
Look at the path B -> E -> D -> B. This is a loop, because the starting node is the also the end. What’s the cost? It’s 10 – 20 + 5 = -5. This means that adding this loop to a path once lowers the cost of the path by 5. Adding it twice would lower the cost by 2 * 5 = 10. So, whatever shortest path you may have come up with, you can make it smaller by going through the loop one more time. BTW there’s no problem with a negative cost path.
The Floyd-Warshall Algorithm
This algorithm calculates the length of the shortest path between all nodes of a graph in O(V3) time. Note that it doesn’t actually find the paths, only their lengths.
Let’s say you have the adjacency matrix of a graph. Assuming no loop of negative values, at this point you have the minimum distance between any two nodes which are connected by an edge.
A B C D EA 0 10 0 5 0B 10 0 5 5 10C 0 5 0 0 0D 5 5 0 0 20E 0 10 0 20 0The graph is the one shown above (the first one).
The idea is to try to interspace A between any two nodes in hopes of finding a shorter path.
A B C D EA 0 10 0 5 0B 10 0 5 5 10C 0 5 0 0 0D 5 5 0 0 20E 0 10 0 20 0Then try to interspace B between any two nodes:
A B C D EA 0 10 155 20B 10 0 5 5 10C 155 0 10 15D 5 5 100 15E 2010 15 150Do the same for C:
A B C D EA 0 10 15 5 20B 10 0 5 5 10C 15 5 0 10 15D 5 5 10 0 15E 20 10 15 15 0Do the same for D:
A B C D EA 0 10 15 5 20B 10 0 5 5 10C 15 5 0 10 15D 5 5 10 0 15E 20 10 15 15 0And for E:
A B C D EA 0 10 15 5 20B 10 0 5 5 10C 15 5 0 10 15D 5 5 10 0 15E 20 10 15 15 0This is the actual algorithm:
# dist(i,j) is "best" distance so far from vertex i to vertex j
# Start with all single edge paths.
For i = 1 to n do
For j = 1 to n do
dist(i,j) = weight(i,j)
For k = 1 to n do # k is the `intermediate' vertex
For i = 1 to n do
For j = 1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then # shorter path?
dist(i,j) = dist(i,k) + dist(k,j)
include
int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
it exists, or 0 if it does not */
void printDist() {
int i, j;
printf(” “);
for (i = 0; i < n; ++i)
printf(“%4c”, ‘A’ + i);
printf(“\n”);
for (i = 0; i < n; ++i) {
printf(“%4c”, ‘A’ + i);
for (j = 0; j < n; ++j)
printf(“%4d”, dist[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*
floyd_warshall()
after calling this function dist[i][j] will the the minimum distance
between i and j if it exists (i.e. if there’s a path between i and j)
or 0, otherwise
*/
void floyd_warshall() {
int i, j, k;
for (k = 0; k < n; ++k) {
printDist();
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
/* If i and j are different nodes and if
the paths between i and k and between
k and j exist, do */
if ((dist[i][k] * dist[k][j] != 0) && (i != j))
/* See if you can’t get a shorter path
between i and j by interspacing
k somewhere along the current
path */
if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
(dist[i][j] == 0))
dist[i][j] = dist[i][k] + dist[k][j];
}
printDist();
}
int main(int argc, char *argv[]) {
FILE *fin = fopen(“dist.txt”, “r”);
fscanf(fin, “%d”, &n);
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fscanf(fin, “%d”, &dist[i][j]);
fclose(fin);
floyd_warshall();
return 0;
}
Techknow_Study 
