**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.

- 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**

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**

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