Advertisement
Shailrshah

Shortest Path with Dijkstra's

Mar 27th, 2014
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.28 KB | None | 0 0
  1. #include <stdio.h>
  2. int main(){
  3.     int weight[10][10], visit[10], min[10], via[10];
  4.     int i, j, k, source, dest, least, n, dd, cost = 0;
  5.     printf("Enter Number Of Nodes: ");
  6.     scanf("%d", &n);
  7.     printf("Enter weights:-\n");
  8.     for(i = 0; i < n; i++)
  9.         for(j = 0; j < n; j++){
  10.             printf("%c-%c: ", 'A'+i, 'A'+j);
  11.             scanf("%d", &weight[i][j]);
  12.         }
  13.     for(i = 0; i < n; i++){
  14.         visit[i] = 0;
  15.         min[i] = 99999;
  16.     }
  17.     printf("Enter Source and Destination indexes:-\n");
  18.     scanf("%d%d", &source, &dest);
  19.     k = source;
  20.     least = 0;
  21.     while(visit[dest] != 2){
  22.         visit[k] = 2;
  23.         for(i = 0; i < n; i++){
  24.             if(weight[k][i] && visit[i] != 2){
  25.                 dd = least + weight[k][i];
  26.                 if(dd < min[i]){
  27.                     min[i] = dd;
  28.                     via[i] = k;
  29.                 }
  30.                 visit[i] = 1;
  31.             }
  32.         }
  33.         least = 99999;
  34.         for(i = 0; i < n; i++)
  35.             if(visit[i] == 1 && min[i] < least){
  36.                 least = min[i];
  37.                 k = i;
  38.             }
  39.     }
  40.     printf("%c -> ",'A'+dest);
  41.     cost += weight[dest][via[dest]];
  42.     for(k = via[dest]; k != source; k = via[k]){
  43.         printf("%c -> ",'A'+k);
  44.         cost += weight[k][via[k]];
  45.     }
  46.     printf("%c",'A'+source);
  47.     printf("\nCost = %d", cost);
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement