Things to be discussed here are,

  • Dijkstra Algorithm
  • Practice Problem

Dijkstra Algorithm

This algorithm helps us to solve single-source shortest-path problems on a weighted directed graph G = (V, E) for the case in which all edge weights are non-negative.

  • This algorithm finds the shortest paths from the starting node to all nodes of the graph, like the Bellman-Ford algorithm.
  • The benefit of Dijkstra’s algorithm is that it has more efficient and can be used for processing large graphs.
  • Dijkstra’s algorithm maintains distances to the nodes and reduces them during the search.
  • This algorithm is efficient because it only processes each edge in the graph once, using the fact there is no negative cycle.

Explanation

Implementation

The following implementation of Dijkstra’s algorithm calculates the minimum distances from a node x to other nodes of the graph.

Fig 1: Example Graph
  • To perform this algorithm store the graph as adjacency lists so that adj[u] contains a pair (v, w) always when there is an edge from node u to node v with weight w.
  • An efficient implementation of Dijkstra’s algorithm requires that it is possible to efficiently find the minimum distance node that has not been processed.
  • An appropriate data structure for this is a priority queue that contains the nodes ordered by their distances.
  • Using a priority queue, the next node to be processed can be retrieved in logarithmic time.
  • Priority queue pq contains the distance of the form (-d,x), meaning that the current distance to node x is d.
  • The array distance contains the distance to each node, and the array processed indicated whether a node has been processed.
  • Initially, the distance is 0 to x and  to all other nodes.
  • The time complexity of this implementation is O( n + mlogm ) where n is the number of nodes and m is the number of edges.

Note:

  • Priority queue contains negative distances to nodes because the default version of the C++ priority queue finds maximum elements, while we want to find minimum elements.
  • By using negative distance we can directly use the default priority queue.
#include <bits/stdc++.h>
#define INF 666
using namespace std;

int main() {
    int n, m;  // n-number of nodes, m-number of edges.
    cin >> n >> m;
    vector<pair<int, int> > g[n + 1];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // storing the given edges into adjecency list.
        g[u].push_back(make_pair(v, w));
    }

    // dijkstra processing by finding distance to all other nodes from the first
    // node - 1
    int dist[n + 1];
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    bool processed[n + 1];  // to check whether the node has been visited
                            // earlier or not.
    for (int i = 1; i <= n; i++) processed[i] = false;
    priority_queue<pair<int, int> >
        pq;  // .first() = weight and .second() = node
    pq.push(make_pair(0, 1));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (processed[u]) continue;
        processed[u] = true;
        for (auto x : g[u]) {
            int v = x.first, w = x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(-dist[v], v));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << 1 << " to " << i << " --> " << dist[i] << "\n";
    }
    return 0;
}

Input:

6 9
1 5 2
1 4 2
5 4 3
5 6 4
4 6 1
4 3 6
2 3 4
4 2 6
2 1 5

Output:

1 to 1 --> 0
1 to 2 --> 8
1 to 3 --> 8
1 to 4 --> 2
1 to 5 --> 2
1 to 6 --> 3

Practice Problem

  1. Dijkstra? ( 20C )
  2. Party ( 115A )
  3. Ice Cave ( 540C )
  4. Road Map ( 34D ) 

That’s all for this article, in the next session we will be discussing Floyd-Warshall Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you. And if there is any error then do comment.

Thank You
With 💙 by Learn DSA

This Post Has One Comment

  1. Md. Shahriar

    4-2 costs should be 6 and 4-6 cost should be 1 in the example graph figure…

Leave a Reply