# C++ Program to Implement Dijkstra’s Algorithm using Priority_queue(Heap)

«
»
This C++ program displays the Djikstra’s Algorithm of finding shortest paths from one node to others using the concept of a priority queue. a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.

Here is the source code of the C++ program to display the shortest distance and the source node associated with the shortest distance. This C++ program is successfully compiled and run on DevCpp,a C++ compiler.The program output is given below.

1. `/*`
2. ` * C++ Program to Implement Dijkstra's Algorithm using Priority_queue(Heap)`
3. ` */`
4. `#include<iostream>`
5. `#include<stdio.h>`
6. `using namespace std;`
7. `#include<conio.h>`
8. `#define INFINITY 999`
9. `struct node`
10. `{`
11. `    int cost;`
12. `    int value;`
13. `    int from;`
14. `}a;`
15. `void min_heapify(int *b, int i, int n)`
16. `{`
17. `    int j, temp;`
18. `    temp = b[i];`
19. `    j = 2 * i;`
20. `    while (j <= n)`
21. `    {`
22. `        if (j < n && b[j + 1] < b[j])`
23. `        {`
24. `            j = j + 1;`
25. `        }`
26. `        if (temp < b[j])`
27. `        {`
28. `            break;`
29. `        }`
30. `        else if (temp >= b[j])`
31. `        {`
32. `            b[j / 2] = b[j];`
33. `            j = 2 * j;`
34. `        }`
35. `    }`
36. `    b[j / 2] = temp;`
37. `    return;`
38. `}`
39. `void build_minheap(int *b, int n)`
40. `{`
41. `    int i;`
42. `    for(i = n / 2; i >= 1; i--)`
43. `    {`
44. `        min_heapify(b, i, n);`
45. `    }`
46. `}`
47. `void addEdge(int am[], int src, int dest, int cost)`
48. `{`
49. `     am[src][dest] = cost;`
50. `     return;`
51. `}`
52. `void bell(int am[])`
53. `{`
54. `    int i, j, k, c = 0, temp;`
55. `    a.cost = 0;`
56. `    a.from = 0;`
57. `    a.value = 0;`
58. `    for (i = 1; i < 7; i++)`
59. `    {`
60. `        a[i].from = 0;`
61. `        a[i].cost = INFINITY;`
62. `        a[i].value = 0;`
63. `    }`
64. `    while (c < 7)`
65. `    {`
66. `        int min = 999;`
67. `        for (i = 0; i < 7; i++)`
68. `        {`
69. `            if (min > a[i].cost && a[i].value == 0)`
70. `            {`
71. `                min = a[i].cost;`
72. `            }`
73. `            else`
74. `            {`
75. `                continue;`
76. `            }`
77. `        }`
78. `        for (i = 0; i < 7; i++)`
79. `        {`
80. `            if (min == a[i].cost && a[i].value == 0)`
81. `            {`
82. `                break;`
83. `            }`
84. `            else`
85. `            {`
86. `                continue;`
87. `            }`
88. `        }`
89. `        temp = i;`
90. `        for (k = 0; k < 7; k++)`
91. `        {`
92. `            if (am[temp][k] + a[temp].cost < a[k].cost)`
93. `            {`
94. `                a[k].cost = am[temp][k] + a[temp].cost;`
95. `                a[k].from = temp;`
96. `            }`
97. `            else`
98. `            {`
99. `                continue;`
100. `            }`
101. `        }`
102. `        a[temp].value = 1;`
103. `        c++;`
104. `    }`
105. `    cout<<"Cost"<<"\t"<<"Source Node"<<endl; `
106. `    for (j = 0; j < 7; j++)`
107. `    {`
108. `        cout<<a[j].cost<<"\t"<<a[j].from<<endl;`
109. `    }`
110. `}`
111. `int main()`
112. `{`
113. `    int n, am, c = 0, i, j, cost;`
114. `    for (int i = 0; i < 7; i++)`
115. `    {`
116. `        for (int j = 0; j < 7; j++)`
117. `        {`
118. `            am[i][j] = INFINITY;`
119. `        }`
120. `    }`
121. `    while (c < 12)`
122. `    {`
123. `        cout<<"Enter the source, destination and cost of edge\n";`
124. `        cin>>i>>j>>cost;`
125. `        addEdge(am, i, j, cost);`
126. `        c++;`
127. `    }`
128. `    bell(am);`
129. `    getch();`
130. `}`

```Output

Enter the source, destination and cost of edge
0
1
3
Enter the source, destination and cost of edge
0
2
6
Enter the source, destination and cost of edge
1
2
2
Enter the source, destination and cost of edge
1
3
4
Enter the source, destination and cost of edge
2
3
1
Enter the source, destination and cost of edge
2
4
4
Enter the source, destination and cost of edge
2
5
2
Enter the source, destination and cost of edge
3
4
2
Enter the source, destination and cost of edge
3
6
4
Enter the source, destination and cost of edge
4
6
1
Enter the source, destination and cost of edge
4
5
2
Enter the source, destination and cost of edge
5
6
1
Cost    Source Node
0       0
3       0
5       1
6       2
8       3
7       2
8       5```

Sanfoundry Global Education & Learning Series – 1000 C++ Programs. 