Things to be discussed here,
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
- 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 there 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.
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