Dijkstra’s Algorithm is popularly used in computing shortest paths from a single source node to all other nodes in a graph. This makes it useful in networks such as maps of cities or routing protocols where each node represents a city and edges represent the roads between them.

When to Use Dijkstra’s Algorithm#

Dijkstra’s Algorithm is ideal for problems involving weighted graphs, whether directed or undirected. Some common applications include:

Finding the shortest driving distance between cities.
Finding the least time-consuming path in a network.
Finding the optimal paths in automated routing systems.

Key Characteristics#

Non-negative Weights#

Dijkstra’s algorithm requires all edge weights to be non-negative. This constraint is crucial because the algorithm uses a greedy approach, picking the next most promising node based on the lowest cumulative weight from the start node.

Dijkstra’s algorithm prioritizes nodes based on the shortest known distance from the start node. If a negative weight is introduced, a longer path could suddenly become shorter than previously calculated paths, leading to incorrect results unless the algorithm is restarted or adjusted, which Dijkstra’s doesn’t handle by default.

Greedy Method#

Dijkstra’s Algorithm uses a greedy technique, meaning it makes the best or most optimal choice at each step as it works towards the final solution.

At every step, the algorithm selects the next node to visit based on which has the shortest accumulated distance from the source. This is managed with a priority queue.

Shortest Path Calculation#

Consider a simple graph where nodes represent cities and edges represent direct roads between them, with weights indicating the distance (in kilometers):

      [A]----4----[B]
       |           |
       8           2
       |           |
      [C]----3----[D]

We need to find the shortest path from city A to all other cities.

Solution#

import heapq as heap

class Solution:


    def dijkstra(self, V, adj, S):
        distance = [float('inf') for i in range(V)]
        visited = set()
        distance[S] = 0
        minHeap = [(0, S)]

        while minHeap:
            currentDistance, currentNode = heap.heappop(minHeap)

            if currentNode in visited:
                continue

            for child, weight in adj[currentNode]:
                nextDistance = currentDistance + weight
                if nextDistance < distance[child]:
                    distance[child] = nextDistance
                    heap.heappush(minHeap, (nextDistance, child))

        return distance