fork(6) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct AL
  4. {
  5.     int data;
  6.     int weight;
  7.     struct AL *next;
  8. };
  9. #define MAX 100000
  10. typedef pair<int,int> P;
  11.  
  12. void addEdge(vector<struct AL *> &G,int start,int end,int weight)
  13. {
  14.     struct AL *temp = (struct AL *)malloc(sizeof(struct AL));
  15.     temp->weight = weight;
  16.     temp->data = end;
  17.     temp->next = G[start];  //G[start] initially contains NULL
  18.     G[start] = temp;    //Now G[start] contains value at temp
  19. }
  20.  
  21. void print(vector<struct AL *> &G,int N)
  22. {
  23.     for(int i=0;i<N;i++)
  24.     {
  25.         struct AL *temp = G[i];
  26.         printf("Node %d ",i);
  27.         while(temp)
  28.         {
  29.             printf(" -> %d ",temp->data);
  30.             temp = temp->next;
  31.         }
  32.         printf("\n");
  33.     }
  34. }
  35.  
  36. class cmp
  37. {	
  38. 	public:
  39. 		bool operator()(P &A,P &B)
  40. 		{
  41. 			return A.second > B.second;
  42. 		}
  43. };
  44.  
  45. void dijkstra(vector<struct AL *> &G,int start,int N)
  46. {
  47.     int distance[N+1],v[N+1],i;
  48.     for(i=0;i<N;i++)
  49.     {
  50. 		distance[i] = MAX;
  51. 		v[i] = 0;
  52. 	}
  53.     distance[start] = 0;
  54. 	priority_queue<P,vector<P >,cmp > PQ;
  55. 	PQ.push(make_pair(start,0));
  56. 	P A;
  57. 	while(!PQ.empty())
  58. 	{
  59. 		A = PQ.top();
  60. 		PQ.pop();
  61. 		int u = A.first;
  62. 		int d = A.second;
  63. 		if(v[u] == 1)
  64. 			continue;
  65. 		v[u] = 1;
  66. 		struct AL *temp = G[u];
  67. 		while(temp)
  68. 		{
  69. 			if(distance[temp->data] > distance[u] + temp->weight)
  70. 				distance[temp->data] = distance[u] + temp->weight;
  71. 			PQ.push(make_pair(temp->data,distance[temp->data]));
  72. 			temp = temp->next;
  73. 		}
  74. 	}
  75.  
  76. 	for(i=0;i<N;i++)
  77. 		printf("%d ",distance[i]);
  78.  
  79. }
  80.  
  81. int main(void)
  82. {
  83.     vector<struct AL *> Graph;
  84.     int v = 5,i;
  85.     for(int i=0;i<v;i++)
  86.         Graph.push_back(NULL);
  87.     addEdge(Graph, 0, 1,10);
  88.     addEdge(Graph, 0, 2,3);
  89.     addEdge(Graph, 1, 2,1);
  90.     addEdge(Graph, 2, 1,4);
  91.     addEdge(Graph, 2, 3,8);
  92.     addEdge(Graph, 1, 3,2);
  93.     addEdge(Graph, 2, 4,2);
  94.     addEdge(Graph, 3, 4,7);
  95.     addEdge(Graph, 4, 3,9);
  96.     dijkstra(Graph,0,v);
  97.     return 0;
  98. }
  99.  
  100.  
  101.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 7 3 9 5
https://ideone.com/o2acci
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!