Dijkstra’s Algorithm

Yasin Cakal

Dijkstra’s algorithm is one of the most well-known algorithms in computer science. It is an algorithm for finding the shortest path between two nodes in a graph. It is an example of a greedy algorithm, meaning that it makes decisions on which path to take based on the immediate rewards it will receive. It’s named after Edsger Dijkstra, who was a Dutch computer scientist.

Dijkstra’s algorithm is widely used in many fields such as robotics, networking, and operations research. It is also often used in data structures and algorithms classes to teach students about graph traversal and shortest path finding. This article will provide an in-depth look at Dijkstra’s algorithm in the context of the Python programming language. We will discuss how the algorithm works, its time and space complexities, and provide sample code that can be used to implement the algorithm.

What Is Dijkstra’s Algorithm?

Dijkstra’s algorithm is an algorithm used to find the shortest path between two nodes in a graph. It can also be used to find the shortest path between all nodes in a graph. The algorithm works by starting at the source node and exploring all of its neighbors. It then visits the neighbor with the lowest cost and continues in this fashion until it reaches the destination node.

The algorithm assigns each node a score, which is the distance from the source node. This score is used to determine which node to visit next. If two nodes have the same score, the algorithm will visit the one with the lowest cost.

Time Complexity

The time complexity of Dijkstra’s algorithm is O(|V|^2), where |V| is the number of nodes in the graph. This means that the algorithm will take longer to run as the number of nodes increases.

In the worst case, the algorithm will visit every node in the graph, which takes O(|V|) time. For each node, the algorithm must explore all of its neighbors, which takes an additional O(|V|) time. Therefore, the total time complexity is O(|V|^2).

Space Complexity

The space complexity of Dijkstra’s algorithm is O(|V|). The algorithm uses an array to keep track of the scores for each node, which takes up O(|V|) space.

Python Code for Dijkstra’s Algorithm

We can use the following Python code to implement Dijkstra’s algorithm:

def dijkstra(graph, source_node):
    # Create an array to store the scores for each node
    scores = [float('inf') for _ in range(len(graph))]
    scores[source_node] = 0
    
    # Create a set to store the visited nodes
    visited = set()
    
    # Loop until all nodes have been visited
    while len(visited) != len(graph):
        # Find the unvisited node with the lowest score
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        # Visit the node with the lowest score
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            # Update the score for each unvisited neighbor
            if neighbor not in visited:
                scores[neighbor] = min(scores[neighbor], scores[lowest_node] + cost)
    
    return scores

Conclusion

Dijkstra’s algorithm is a powerful and efficient algorithm for finding the shortest path between two nodes in a graph. It has a time complexity of O(|V|^2) and a space complexity of O(|V|). It is used in many fields and is a popular topic in data structures and algorithms classes. The code provided in this article can be used as a starting point for implementing the algorithm in Python.

Exercises

Create a function that takes in a graph and a source node and returns the number of nodes visited by the algorithm.

def num_nodes_visited(graph, source):
    visited = set()
    scores = [float('inf') for _ in range(len(graph))]
    scores[source] = 0
    
    while len(visited) != len(graph):
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            if neighbor not in visited:
                scores[neighbor] = min(scores[neighbor], scores[lowest_node] + cost)
    
    return len(visited)

Create a function that takes in a graph, a source node, and a destination node and returns the shortest path from the source to the destination.

def shortest_path(graph, source, destination):
    visited = set()
    scores = [float('inf') for _ in range(len(graph))]
    scores[source] = 0
    paths = [[] for _ in range(len(graph))]
    paths[source].append(source)
    
    while len(visited) != len(graph):
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            if neighbor not in visited:
                if scores[neighbor] > scores[lowest_node] + cost:
                    scores[neighbor] = scores[lowest_node] + cost
                    paths[neighbor] = paths[lowest_node] + [neighbor]
    
    return paths[destination]

Create a function that takes in a graph and a source node and returns a dictionary of all the shortest paths from the source to each node.

def all_shortest_paths(graph, source):
    visited = set()
    scores = [float('inf') for _ in range(len(graph))]
    scores[source] = 0
    paths = [[] for _ in range(len(graph))]
    paths[source].append(source)
    
    while len(visited) != len(graph):
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            if neighbor not in visited:
                if scores[neighbor] > scores[lowest_node] + cost:
                    scores[neighbor] = scores[lowest_node] + cost
                    paths[neighbor] = paths[lowest_node] + [neighbor]
    
    return {node: paths[node] for node in range(len(graph))}

4. Create a function that takes in a graph, a source node, and a destination node and returns the total cost of the shortest path from the source to the destination.

def total_cost(graph, source, destination):
    visited = set()
    scores = [float('inf') for _ in range(len(graph))]
    scores[source] = 0
    
    while len(visited) != len(graph):
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            if neighbor not in visited:
                scores[neighbor] = min(scores[neighbor], scores[lowest_node] + cost)
    
    return scores[destination]

Create a function that takes in a graph and a source node and returns a dictionary of all the shortest paths from the source to each node and their total costs.

def all_shortest_paths_costs(graph, source):
    visited = set()
    scores = [float('inf') for _ in range(len(graph))]
    scores[source] = 0
    paths = [[] for _ in range(len(graph))]
    paths[source].append(source)
    
    while len(visited) != len(graph):
        lowest_score = float('inf')
        lowest_node = None
        for node, score in enumerate(scores):
            if node not in visited and score < lowest_score:
                lowest_score = score
                lowest_node = node
        
        visited.add(lowest_node)
        for neighbor, cost in enumerate(graph[lowest_node]):
            if neighbor not in visited:
                if scores[neighbor] > scores[lowest_node] + cost:
                    scores[neighbor] = scores[lowest_node] + cost
                    paths[neighbor] = paths[lowest_node] + [neighbor]
    
    return {node: (paths[node], scores[node]) for node in range(len(graph))}

Data Structures and Algorithms with Python

Participants 445