C++ Program to Implement Dijkstra’s Algorithm using Priority Queue

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.

```
/*
```

 * C++ Program to Implement Dijkstra's Algorithm using Priority_queue(Heap)

```
 */
```
```
#include<iostream>
```
```
#include<stdio.h>
```
```
using namespace std;
```
```
#include<conio.h>
```
```
#define INFINITY 999
```
```
struct node
```
```
{
```
```
    int cost;
```
```
    int value;
```
```
    int from;
```
```
}a[7];
```
```
void min_heapify(int *b, int i, int n)
```
```
{
```
```
    int j, temp;
```
```
    temp = b[i];
```
```
    j = 2 * i;
```
```
    while (j <= n)
```
```
    {
```
```
        if (j < n && b[j + 1] < b[j])
```
```
        {
```
```
            j = j + 1;
```
```
        }
```
```
        if (temp < b[j])
```
```
        {
```
```
            break;
```
```
        }
```
```
        else if (temp >= b[j])
```
```
        {
```
```
            b[j / 2] = b[j];
```
```
            j = 2 * j;
```
```
        }
```
```
    }
```
```
    b[j / 2] = temp;
```
```
    return;
```
```
}
```
```
void build_minheap(int *b, int n)
```
```
{
```
```
    int i;
```
```
    for(i = n / 2; i >= 1; i--)
```
```
    {
```
```
        min_heapify(b, i, n);
```
```
    }
```
```
}
```

void addEdge(int am[][7], int src, int dest, int cost)

```
{
```
```
     am[src][dest] = cost;
```
```
     return;
```
```
}
```
```
void bell(int am[][7])
```
```
{
```
```
    int i, j, k, c = 0, temp;
```
```
    a[0].cost = 0;
```
```
    a[0].from = 0;
```
```
    a[0].value = 0;
```
```
    for (i = 1; i < 7; i++)
```
```
    {
```
```
        a[i].from = 0;
```
```
        a[i].cost = INFINITY;
```
```
        a[i].value = 0;
```
```
    }
```
```
    while (c < 7)
```
```
    {
```
```
        int min = 999;
```
```
        for (i = 0; i < 7; i++)
```
```
        {
```

            if (min > a[i].cost && a[i].value == 0)

```
            {
```
```
                min = a[i].cost;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        for (i = 0; i < 7; i++)
```
```
        {
```

            if (min == a[i].cost && a[i].value == 0)

```
            {
```
```
                break;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        temp = i;
```
```
        for (k = 0; k < 7; k++)
```
```
        {
```

            if (am[temp][k] + a[temp].cost < a[k].cost)

```
            {
```

                a[k].cost = am[temp][k] + a[temp].cost;

```
                a[k].from = temp;
```
```
            }
```
```
            else
```
```
            {
```
```
                continue;
```
```
            }
```
```
        }
```
```
        a[temp].value = 1;
```
```
        c++;
```
```
    }
```

    cout<<"Cost"<<"\t"<<"Source Node"<<endl;

```
    for (j = 0; j < 7; j++)
```
```
    {
```

        cout<<a[j].cost<<"\t"<<a[j].from<<endl;

```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int n, am[7][7], c = 0, i, j, cost;
```
```
    for (int i = 0; i < 7; i++)
```
```
    {
```
```
        for (int j = 0; j < 7; j++)
```
```
        {
```
```
            am[i][j] = INFINITY;
```
```
        }
```
```
    }
```
```
    while (c < 12)
```
```
    {
```

        cout<<"Enter the source, destination and cost of edge\n";

```
        cin>>i>>j>>cost;
```
```
        addEdge(am, i, j, cost);
```
```
        c++;
```
```
    }
```
```
    bell(am);
```
```
    getch();
```
```
}
```

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.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Bellman Ford Algorithm

» Next - Inorder Tree Traversal without using Recursion in C++

Related Posts:

Recommended Articles: