dijkstra algorithm.
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
Path 2
Path 3
Path 4
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
20B 10 0 5 5 10
C
15
5 0
10
15D 5 5
10
0
15E
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;
}
0 comments