fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define N 6
  5. #define INF 9999
  6.  
  7. int flag[N + 1];
  8. int dist[N + 1];
  9. int index[N + 1];
  10.  
  11. int min, position;
  12.  
  13. int data[N + 1][N + 1] = 
  14. {{0, 0, 0, 0, 0, 0, 0},
  15. {0, 0, 2,INF, 3,INF,INF},
  16. {0,INF, 0, 4 , 1, 7,INF},
  17. {0,INF,INF, 0, 4, 1, 3},
  18. {0,INF, 2, 2, 0, 1,INF},
  19. {0,INF,INF, 1,INF, 0, 6},
  20. {0,INF, 3,INF, 8,INF, 0}};
  21.  
  22. int main()
  23. {
  24.    for (int i = 1; i <= N; i++) {
  25.       flag[i] = 0;
  26.       dist[i] = INF;
  27.    }
  28.  
  29.    dist[1] = 0;
  30.  
  31.    for (int i = 1; i <= N; i++) {
  32.       min = INF;
  33.       for (int j = 1; j <= N; j++) {
  34.          if (min > dist[j] && flag[j] == 0) {
  35.             min = dist[j] + data[j][0];
  36.             position = j;
  37.          }
  38.       }
  39.       flag[position] = 1;
  40.       for (int j = 1; j <= N; j++) {
  41.          if (dist[j] > dist[position] + data[position][j] && data[position][j] != INF) {
  42.             dist[j] = dist[position] + data[position][j];
  43.             index[j] = position;
  44.          }
  45.       }
  46.    }
  47.    for (int i = 1; i <= N; i++) {
  48.       printf("1 ~ %d : %d Path: %d", i, dist[i], i);
  49.       position = i;
  50.       do {
  51.          printf(" <- %d", index[position]);
  52.          position = index[position];
  53.       } while (index[position]);
  54.       puts("");
  55.    }
  56. }
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 ~ 1 : 0 Path: 1 <- 0
1 ~ 2 : 2 Path: 2 <- 1
1 ~ 3 : 5 Path: 3 <- 4 <- 1
1 ~ 4 : 3 Path: 4 <- 1
1 ~ 5 : 4 Path: 5 <- 4 <- 1
1 ~ 6 : 8 Path: 6 <- 3 <- 4 <- 1
https://ideone.com/mRmVKX
language:
C (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!