fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #define V 9
  3. using namespace std;
  4. bool Left[V];
  5. int Distances[V];
  6. int find(int start)
  7. {
  8.     int low=INT_MAX,idx=-1,i;
  9.     for(i=0;i<V;i++)
  10.         if( !(Left[i]) && low>=Distances[i])
  11.             {
  12.                 idx=i;
  13.                 low=Distances[i];
  14.             }
  15.     return idx;
  16. }
  17. void djikstra(int start,int graph[V][V])
  18. {
  19.     int i,j,k;
  20.     for(i=0;i<V;i++)
  21.         Distances[i]=INT_MAX;
  22.     Distances[start]=0;
  23.     Left[start]=true;
  24.     while(start!=-1)
  25.     {
  26.         for(i=0;i<V;i++)
  27.             if(graph[start][i] && Distances[start]+graph[start][i]<Distances[i]  )
  28.                 Distances[i]=graph[start][i]+Distances[start];
  29.         start=find(start);
  30.         Left[start]=true;
  31.     }
  32. }
  33. int main()
  34. {
  35.     int i;
  36.    /* Let us create the example graph discussed above */
  37.    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
  38.                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
  39.                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
  40.                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
  41.                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
  42.                       {0, 0, 4, 0, 10, 0, 2, 0, 0},
  43.                       {0, 0, 0, 14, 0, 2, 0, 1, 6},
  44.                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
  45.                       {0, 0, 2, 0, 0, 0, 6, 7, 0}
  46.                     };
  47.     djikstra(0,graph);
  48.     for(i=0;i<V;i++)
  49.         printf("%d ",Distances[i]);
  50.  
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 4 12 19 21 11 9 8 16777230
https://ideone.com/0uuUbY
language:
C++ (gcc 8.3)
created:
10 years 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!