Techknow Study

dijkstra algorithm.

8:09:00 AM vikas 0 Comments Category :

            WAP in C/C++ to find the shortest route using dijkstra algorithm.

THEORY & CONCEPT-:
The shortest path between 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: A -> B -> E 20
Path 2: A -> D -> E 25
Path 3: A -> B -> D -> E 35
Path 4: A -> D -> B -> E 20

There 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 E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0
The 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 E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0
Then try to interspace B between any two nodes:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
Do the same for C:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
Do the same for D:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
And for E:
A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

This 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 <stdio.h>   
  
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;   
}

RELATED POSTS

0 comments