fork download
copy 
  1. #include <stdio.h>
  2. #define INF 999
  3. #define MAX 20
  4. int main() {
  5.  int n, s, cost[MAX][MAX], dist[MAX], visited[MAX] = {0};
  6.  int i, j, count;
  7.  printf("Enter the number of vertices: ");
  8.  scanf("%d", &n);
  9.  printf("Enter the weighted matrix:\n");
  10.  for (i = 0; i < n; i++)
  11.  for (j = 0; j < n; j++)
  12.  scanf("%d", &cost[i][j]);
  13.  printf("Enter the source vertex: ");
  14.  scanf("%d", &s);
  15.  for (i = 0; i < n; i++)
  16.  dist[i] = cost[s][i];
  17.  dist[s] = 0;
  18.  visited[s] = 1;
  19.  for (count = 1; count < n; count++) {
  20.  int min = INF, u = -1;
  21.  for (i = 0; i < n; i++)
  22.  if (!visited[i] && dist[i] < min) {
  23.  min = dist[i];
  24.  u = i;
  25.  }
  26.  if (u == -1)
  27.  break;
  28.  visited[u] = 1;
  29.  for (i = 0; i < n; i++)
  30.  if (!visited[i] && cost[u][i] != INF &&
  31.  dist[u] + cost[u][i] < dist[i])
  32.  dist[i] = dist[u] + cost[u][i];
  33.  }
  34.  printf("The shortest path between source %d to remaining vertices are:\n", s);
  35.  for (i = 0; i < n; i++)
  36.  if (i != s)
  37.  printf("%d -> %d = %d\n", s, i, dist[i]);
  38.  return 0;
  39. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter the number of vertices: Enter the weighted matrix:
Enter the source vertex: The shortest path between source 0 to remaining vertices are:
0 -> 1 = 0
0 -> 2 = 0
https://ideone.com/NVnjUb
language:
C (gcc 8.3)
created:
6 hours 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!