fork 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()
  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;
  20.     for(i=0;i<V;i++)
  21.         Distances[i]=INT_MAX;
  22.     Distances[start]=0;
  23.     while(start!=-1)
  24.     {
  25.         Left[start]=true;
  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();
  30.     }
  31. }
  32. int main()
  33. {
  34.     int i;
  35.    /* Let us create the example graph discussed above */
  36.    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
  37.                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
  38.                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
  39.                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
  40.                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
  41.                       {0, 0, 4, 0, 10, 0, 2, 0, 0},
  42.                       {0, 0, 0, 14, 0, 2, 0, 1, 6},
  43.                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
  44.                       {0, 0, 2, 0, 0, 0, 6, 7, 0}
  45.                     };
  46.     djikstra(0,graph);
  47.     for(i=0;i<V;i++)
  48.         printf("%d ",Distances[i]);
  49.  
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 4 12 19 21 11 9 8 14
https://ideone.com/v6rWrF
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!