Dijkstra Algorithm

Dijkstra Algorithm#

Dijkstra’s algorithm finds the shortest paths from a single source node to all other nodes in a weighted graph with non-negative weights. It is more efficient than Bellman-Ford for graphs with non-negative weights.

Key Components#

Initialisation:

  1. Initialise the distance dictionary with infinite values for all nodes except the start node, which is set to 0.

  2. Initialise the predecessor dictionary with None for all nodes.

def dijkstra(network, start):
    unvisited = {node: float('infinity') for node in network}
    visited = {}
    current = start
    current_distance = 0
    unvisited[current] = current_distance
    predecessors = {node: None for node in network}

Relaxation:

  1. For the current node, update the distances to its neighbours if a shorter path is found. Update the predecessors dictionary accordingly.

    while True:
        for neighbor, weight in network[current].items():
            if neighbor not in unvisited: continue
            new_distance = current_distance + weight
            if unvisited[neighbor] > new_distance:
                unvisited[neighbor] = new_distance
                predecessors[neighbor] = current

Node Selection:

  1. Mark the current node as visited and select the next unvisited node with the smallest distance.

        visited[current] = current_distance
        del unvisited[current]
        if not unvisited: break
        candidates = [node for node in unvisited.items() if node[1]]
        current, current_distance = sorted(candidates, key=lambda x: x[1])[0]

Return Result:

  1. Return the visited and predecessors dictionaries.

    return visited, predecessors

Path Reconstruction:

  1. To reconstruct the path from the start node to any other node, follow the predecessors dictionary from the end node to the start node.

def get_path_dijkstra(source, destination, network):
    distances, predecessors = dijkstra(network, source)
    path = []
    node = destination
    while node != source:
        if node is None:
            print("Path doesn't exist.")
            return
        path.append(node)
        node = predecessors[node]
    path.append(source)
    path.reverse()
    return path, distances[destination]

The output from running the code is below:#

Shortest path from A to H: A -> B -> D -> H
Total distance: 5
Shortest path from D to H: D -> H
Total distance: 2
Shortest path from B to E: B -> F -> E
Total distance: 3

View the full code:#

# Define a network of routers with their neighbours and associated costs (distances).
routers = {
    'A': {'B': 1, 'C': 2, 'E': 3},
    'B': {'A': 1, 'C': 1, 'D': 2, 'F': 2},
    'C': {'A': 2, 'B': 1, 'D': 1, 'G': 3},
    'D': {'B': 2, 'C': 1, 'H': 2},
    'E': {'A': 3, 'F': 1},
    'F': {'B': 2, 'E': 1, 'G': 1},
    'G': {'C': 3, 'F': 1, 'H': 2},
    'H': {'D': 2, 'G': 2},
}


# Use Bellman-Ford Algorithm to find the shortest route from a start node to all other nodes in the network.
def dijkstra(network, start):
    unvisited = {node: float('infinity') for node in network}
    visited = {}
    current = start
    current_distance = 0
    unvisited[current] = current_distance

    predecessors = {node: None for node in network}

    while True:
        for neighbor, weight in network[current].items():
            if neighbor not in unvisited: continue
            new_distance = current_distance + weight
            if unvisited[neighbor] > new_distance:
                unvisited[neighbor] = new_distance
                predecessors[neighbor] = current

        visited[current] = current_distance
        del unvisited[current]

        if not unvisited: break

        candidates = [node for node in unvisited.items() if node[1]]
        current, current_distance = sorted(candidates, key=lambda x: x[1])[0]

    return visited, predecessors


# Use the output from the Bellman-Ford algorithm to trace
# back and determine the shortest path from source to destination.
def get_path(source, destination, network):
    distances, predecessors = dijkstra(network, source)
    path = [] # Store the shortest path nodes.
    node = destination
    while node != source:
        if node is None:
            print("Path doesn't exist.")
            return
        path.append(node)
        node = predecessors[node]
    path.append(source)
    path.reverse()
    return path, distances[destination]


# Test the algorithm and find the paths between specific routers
if __name__ == "__main__":
    source, destination = 'A', 'H'
    path, distance = get_path(source, destination, routers)
    print(f"Shortest path from {source} to {destination}: {' -> '.join(path)}")
    print(f"Total distance: {distance}")

    source, destination = 'D', 'H'
    path, distance = get_path(source, destination, routers)
    print(f"Shortest path from {source} to {destination}: {' -> '.join(path)}")
    print(f"Total distance: {distance}")

    source, destination = 'B', 'E'
    path, distance = get_path(source, destination, routers)
    print(f"Shortest path from {source} to {destination}: {' -> '.join(path)}")
    print(f"Total distance: {distance}")
Contents