fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define INF 99999
  4.  
  5. int main()
  6. {
  7.     int n, cost[10][10], dist[10], visited[10];
  8.     int i, j, u, min, src;
  9.  
  10.     printf("Enter number of vertices: ");
  11.     scanf("%d", &n);
  12.  
  13.     printf("Enter adjacency matrix (use %d for INF):\n", INF);
  14.     for (i = 0; i < n; i++)
  15.         for (j = 0; j < n; j++)
  16.             scanf("%d", &cost[i][j]);
  17.  
  18.     printf("Enter source vertex (0 to %d): ", n - 1);
  19.     scanf("%d", &src);
  20.  
  21.     // Initialize
  22.     for (i = 0; i < n; i++) {
  23.         dist[i] = cost[src][i];
  24.         visited[i] = 0;
  25.     }
  26.  
  27.     dist[src] = 0;
  28.     visited[src] = 1;
  29.  
  30.     // Dijkstra
  31.     for (i = 0; i < n - 1; i++) {
  32.  
  33.         min = INF;
  34.         u = -1;
  35.  
  36.         for (j = 0; j < n; j++) {
  37.             if (!visited[j] && dist[j] < min) {
  38.                 min = dist[j];
  39.                 u = j;
  40.             }
  41.         }
  42.  
  43.         if (u == -1) break;    // <-- Prevent infinite loop
  44.  
  45.         visited[u] = 1;
  46.  
  47.         for (j = 0; j < n; j++) {
  48.             if (!visited[j] && dist[j] > dist[u] + cost[u][j]) {
  49.                 dist[j] = dist[u] + cost[u][j];
  50.             }
  51.         }
  52.     }
  53.  
  54.     // Output
  55.     printf("\nShortest distances from source %d:\n", src);
  56.     for (i = 0; i < n; i++)
  57.         printf("%d → %d = %d\n", src, i, dist[i]);
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter number of vertices: Enter adjacency matrix (use 99999 for INF):
Enter source vertex (0 to -1): 
Shortest distances from source 0:
https://ideone.com/rzGbn5
language:
C (gcc 8.3)
created:
7 days ago
visibility:
public

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!