SHARE
TWEET

Untitled

a guest Dec 8th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include<climits>
  3. using namespace std;
  4. #define V 7
  5.  
  6. int minKey(int key[],bool spSet[])
  7. {
  8.     int min = INT_MAX,min_index;
  9.     for(int i=0;i<V;i++)
  10.     {
  11.         if(spSet[i]==false && key[i]<min)
  12.         {
  13.             min = key[i],min_index=i;
  14.         }
  15.     }
  16.     return min_index;
  17. }
  18.  
  19. void dijkstra(int graph[V][V],int src)
  20. {
  21.     int key[V];
  22.     bool spSet[V] ;
  23.     for(int i=0;i<V;i++)
  24.     {
  25.         spSet[i]=false , key[i] = INT_MAX ;
  26.     }
  27.     key[src]=0;
  28.     for(int count=0;count<V;count++)
  29.     {
  30.         int u = minKey(key,spSet);
  31.         spSet[u] = true ;
  32.         for(int v=0;v<V;v++)
  33.         {
  34.             if(!spSet[v] && graph[u][v] && spSet[v]!=INT_MAX && key[v] > key[u]+graph[u][v])
  35.             {
  36.                 key[v] = key[u]+graph[u][v] ;
  37.             }
  38.         }
  39.     }
  40.     cout << "VERTICES\t\tEDGES DISTANCE FROM: " << endl;
  41.     for(int i=0;i<V;i++)
  42.     {
  43.         char c=65+i;
  44.         cout << c << "\t\t" << key[i] << endl;
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     int graph[V][V] =  {{0,5,3,0,0,0,0},
  51.                         {0,0,2,0,3,0,1},
  52.                         {0,0,0,7,7,0,0},
  53.                         {0,0,0,0,0,6,0},
  54.                         {0,0,0,2,0,1,0},
  55.                         {0,0,0,0,0,0,0},
  56.                         {0,0,0,0,1,0,0}};
  57.  
  58.             dijkstra(graph,0) ;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top