Dijkstra's algorithm is used to solve the single-source shortest-path problem for a graph having non-negative weights of edges. This algorithm starts at the source vertex. In every iteration, it expands with the neighboring vertices that are reachable from the source. The distances of the vertices are updated by the minimum distance between the source and the corresponding vertex.
Dijkstra's Algorithm (G, w, s)
1
2
3
4
5
6
7
8
9
10
Initialize Single-Source (G, s)
S <- { }
Initialize priority queue Q by all the vertices of the Graph
while priority queue Q is not empty do
u <- Extract-Min(Q)
S <- S U {u}
for each vertex v in Adj[u] do
Relax (u, v, w)
Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
void dijstra(int n, int v, int **cost, int *dist)
{
int i, u, count, w, *flag, min;
flag = (int *)malloc(n * sizeof(int));
for (i = 0; i < n; i++)
flag[i] = 0, dist[i] = cost[v][i];
count = 1;
while (count < n) {
min = 999;
for (w = 0; w < n; w++)
if (dist[w] < min && !flag[w])
min = dist[w], u = w;
flag[u] = 1;
count++;
for (w = 0; w < n; w++)
if ((dist[u] + cost[u][w] < dist[w]) && !flag[w])
dist[w] = dist[u] + cost[u][w];
}
}
int main() {
int n, v, i, j, **cost, *dist;
printf("\n Enter the number of nodes:");
scanf("%d", &n);
cost = (int **)malloc(n * sizeof(int *));
for(i = 0; i < n; i++)
cost[i] = (int *)malloc(n * sizeof(int));
dist = (int *)malloc(n * sizeof(int));
printf("\n Enter the cost matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = INT_MAX;
}
}
printf("\n Enter the source node:");
scanf("%d", &v);
dijstra(n, v, cost, dist);
printf("\n Shortest path:\n");
for (i = 0; i < n; i++)
if (i != v)
printf("%d->%d,cost=%d\n", v, i, dist[i]);
return 0;
}
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.