Guest User

Untitled

a guest
Dec 8th, 2019
87
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