fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits.h>
  4.  
  5. using namespace std;
  6.  
  7. class Graph{
  8.   int V;
  9.   vector<int> *adj;
  10.  
  11.   public:
  12.     Graph(int V);
  13.     void AddEdge(int v, int w);
  14.     void Dijkstra(int src);
  15.     int MinDistance(int dist[], bool sptset[]);
  16.     void PrintGraph(int dist[], int n);
  17. };
  18.  
  19. Graph::Graph(int V){      // construtor
  20.   this->V = V;
  21.   adj = new vector<int> [V];
  22. }
  23.  
  24. void Graph::AddEdge(int v, int w){
  25.   if(v >= 0 && v< V)
  26.     adj[v].push_back(w);
  27. }
  28.  
  29. int Graph::MinDistance(int dist[], bool sptset[]){
  30.   int min = INT_MAX, min_index;
  31.  
  32.   for(int v=0;v<V;v++)
  33.     if(sptset[v] == false && dist[v] <= min)
  34.       min = dist[v], min_index = v;
  35.  
  36.   return min_index;
  37. }
  38.  
  39. void Graph::PrintGraph(int dist[], int n){
  40.   for(int i=0;i<n;i++)
  41.     cout<<i<<" "<<dist[i]<<endl;
  42. }
  43.  
  44. void Graph::Dijkstra(int src){
  45.   int dist[V];
  46.   bool sptset[V];
  47.  
  48.   for(int i=0;i<V;i++)
  49.     dist[i] = INT_MAX, sptset[i] = false;
  50.  
  51.   dist[src] = 0;
  52.  
  53.   //find shortest path for all vertices
  54.   for(int count=0; count< V-1;count++){
  55.     int u = MinDistance(dist,sptset);
  56.  
  57.     sptset[u] = true;
  58.  
  59.     //update dist value of the ajacent vertices 
  60.     for(int v=0;v<adj[u].size();v++){
  61.       if(!sptset[v] && adj[u][v] && dist[u] != INT_MAX 
  62.           && dist[u] + adj[u][v] < dist[v])
  63.         dist[v] = dist[u] + adj[u][v];
  64.     }
  65.   }
  66.   PrintGraph(dist,V);
  67. }
  68.  
  69. int main(){
  70.   Graph g(3);
  71.   g.AddEdge(0,2);
  72.   g.AddEdge(0,3);
  73.   g.Dijkstra(0);
  74.   return 0;
  75. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
1 3
2 2147483647
https://ideone.com/jHlybx
language:
C++14 (gcc 8.3)
created:
8 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!