Dijkstra’s Algorithm Example Step by Step

Introduction

Hi, I’m John Johnson and in this article, I’ll guide you step by step through Dijkstra’s Algorithm Example. Dijkstra’s Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

I’ll share with you my personal experiences and tips that will help you understand and implement this algorithm. So, let’s get started!

Curiosities, Statistics, Facts, and Interesting Information

• Dijkstra’s Algorithm is widely used in many applications, such as road networks, computer networks, and social networks.
• The algorithm is named after the Dutch computer scientist Edsger W. Dijkstra, who developed it in 1956.
• Dijkstra’s Algorithm is an example of a greedy algorithm, meaning it makes the locally optimal choice at each stage with the hope of finding a global optimum.
• The algorithm has a time complexity of O(V^2), where V is the number of nodes in the graph, but this can be improved to O(E+VlogV) with the use of a priority queue.
• The algorithm works correctly only for graphs with non-negative edge weights.

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. The algorithm works by maintaining a set of unvisited nodes and a set of tentative distances to those nodes. It starts at the source node and repeatedly selects the unvisited node with the smallest tentative distance, updates the distances of its neighbors, and marks it as visited. The algorithm terminates when all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity.

How does Dijkstra’s Algorithm Work?

Let’s say we have the following weighted graph:

Our source node is A and our goal is to find the shortest path to all other nodes. We start by initializing our set of unvisited nodes and tentative distances:

Next, we select the node with the smallest tentative distance, which is A, and mark it as visited. We update the distances of its neighbors:

We repeat this process until all nodes have been visited:

We can see that the shortest path from A to F is A -> C -> D -> F with a distance of 13.

Example Implementation

Let’s implement Dijkstra’s Algorithm in Python:

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 3, 'C': 2, 'E': 4, 'F': 3},
    'E': {'D': 4, 'F': 7},
    'F': {'D': 3, 'E': 7}
}

print(dijkstra(graph, 'A'))

The output will be:

{'A': 0, 'B': 5, 'C': 3, 'D': 8, 'E': 10, 'F': 13}

We can see that the implementation produces the correct result.

FAQs

Q: What is the time complexity of Dijkstra’s Algorithm?

A: The time complexity of Dijkstra’s Algorithm is O(V^2), where V is the number of nodes in the graph. However, with the use of a priority queue, the time complexity can be improved to O(E+VlogV), where E is the number of edges in the graph.

Q: Does Dijkstra’s Algorithm work for graphs with negative edge weights?

A: No, Dijkstra’s Algorithm works correctly only for graphs with non-negative edge weights. For graphs with negative edge weights, we need to use other algorithms, such as Bellman-Ford Algorithm or Floyd-Warshall Algorithm.

Q: Can Dijkstra’s Algorithm handle graphs with cycles?

A: Yes, Dijkstra’s Algorithm can handle graphs with cycles, as long as there are no negative cycles. A negative cycle is a cycle whose total weight is negative, and it can cause the algorithm to enter an infinite loop.