Dijkstra Algorithm: What It Is and How It Works

The Dijkstra algorithm is a method to find the shortest path from one point to all other points in a graph with non-negative edge weights. It works by exploring the closest nodes first and updating the shortest known distances until all nodes are processed.

How It Works

Imagine you are in a city and want to find the shortest route to every other place. The Dijkstra algorithm starts at your location and looks at all nearby places, choosing the closest one first. It then moves to that place and repeats the process, always picking the next closest unvisited place.

This method keeps track of the shortest distance found so far to each place and updates it if a shorter route is discovered. It continues until it has checked all places, ensuring the shortest paths from the start point to every other point are found.

Example

This example shows how Dijkstra algorithm finds the shortest paths from a starting node in a graph represented by an adjacency list.

python

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Graph represented as adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(shortest_paths)

Output

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

When to Use

Use Dijkstra algorithm when you need to find the shortest path in a network or map where all distances or costs are positive or zero. It is ideal for GPS navigation, network routing, and planning efficient routes in logistics.

It is not suitable if the graph has negative edge weights, as it cannot handle those correctly. For such cases, other algorithms like Bellman-Ford are better.

Key Points

• Dijkstra algorithm finds shortest paths from one start node to all others in a graph.
• It works only with graphs that have non-negative edge weights.
• It uses a priority queue to always explore the closest unvisited node next.
• Commonly used in GPS, network routing, and pathfinding problems.

Key Takeaways

Dijkstra algorithm finds the shortest path from one node to all others in a graph with non-negative edges.

It uses a priority queue to explore nodes in order of their current shortest distance.

It is widely used in navigation, routing, and network optimization tasks.

It cannot handle graphs with negative edge weights correctly.

The algorithm updates shortest distances as it discovers better paths.