What is Dijkstra Algorithm?

The Dijkstra Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. The algorithm is named after its discoverer, Dutch computer scientist Edsger W. Dijkstra.

Features of dijkstra algorithm

  • It is a greedy algorithm that finds the shortest path from a starting node to all other nodes in a graph.
  • It uses a priority queue to keep track of the nodes that have been visited and the shortest distance to them.
  • It is not guaranteed to find the shortest path if there are multiple shortest paths.
  • It guarantees to find the shortest path from a given starting node to all other nodes in the graph, given that the graph does not contain any negative weight cycles.

Examples of dijkstra algorithm

1. Find the shortest path from node A to node B in a graph.

def dijkstra(graph, A, B):
    # create a set of visited nodes
    visited = set()
    # create a set of nodes to be visited
    unvisited = set(graph.keys())
    # create a dictionary of distances
    distance = {}
    # create a dictionary of predecessors
    predecessor = {}
    # assign the distance from A to A to be 0
    distance[A] = 0
    # assign the predecessor of A to be None
    predecessor[A] = None
    # while there are unvisited nodes
    while unvisited:
        # find the node with the smallest distance in the set of unvisited nodes
        current = min(unvisited, key=lambda k: distance[k])
        # remove the node from the set of unvisited nodes
        unvisited.remove(current)
        # if the distance of the current node is infinity, there is no path to the end node
        if distance[current] == float('inf'):
            break
        # for each neighbor of the current node
        for neighbor in graph[current]:
            # if the neighbor is not visited
            if neighbor not in visited:
  # if the distance to the neighbor is greater than the distance to the current node plus the edge weight
                if distance[neighbor] > distance[current] + graph[current][neighbor]:
                    # update the distance to the neighbor
                    distance[neighbor] = distance[current] + graph[current][neighbor]
                    # update the predecessor of the neighbor
                    predecessor[neighbor] = current
        # add the current node to the set of visited nodes
        visited.add(current)
    # if the distance to the end node is infinity, there is no path to the end node
    if distance[B] == float('inf'):
        return None
    # create a list of nodes that are on the shortest path from the start node to the end node
    path = []
    # set the current node to be the end node
    current = B
    # while the current node has a predecessor
    while current:
        # add the current node to the list of nodes
        path.append(current)

2. Find the shortest path from node A to all other nodes in a graph.

def dijkstra(graph, start):
    # initialize the distance to start node to 0
    distance = {start: 0}
    # initialize the set of visited nodes to empty
    visited = set()
    # initialize the set of unvisited nodes to all nodes in the graph
    unvisited = set(graph.keys())
    # while there are unvisited nodes
    while unvisited:
        # find the node with the smallest distance in the set of unvisited nodes
        current = min(unvisited, key=lambda x: distance[x])
        # add the node to the set of visited nodes
        visited.add(current)
        # remove the node from the set of unvisited nodes
        unvisited.remove(current)
        # for each node in the current node's adjacency list
        for neighbor in graph[current]:
            # if the distance to the neighbor is infinite
            if neighbor not in distance:
            # set the distance to the neighbor to the distance to the current node plus the edge weight
                distance[neighbor] = distance[current] + graph[current][neighbor]
    # return the distance dictionary
    return distance

3. Find the shortest path from node A to node B in a weighted graph.

def dijkstra(graph, start, goal):
    # keep track of all the nodes
    nodes = [start]
    # keep track of all the paths
    paths = {start: [start]}
    # keep track of all the shortest paths
    shortest_paths = {start: 0}
    # keep track of all the shortest paths
    visited = set()
    # keep looping until all the nodes have been visited
    while nodes:
        # sort the nodes
        nodes.sort(key=lambda x: shortest_paths[x])
        # get the first node
        current_node = nodes.pop(0)
        # check if the current node is the goal
        if current_node == goal:
            return paths[current_node]
        # check if the current node has already been visited
        if current_node in visited:
            continue
        # get the neighbors of the current node
        neighbors = graph[current_node]
        # loop over the neighbors
        for neighbor in neighbors:
            # get the edge weight
            edge_weight = neighbors[neighbor]
            # get the total distance from the start node to the neighbor
            total_distance = shortest_paths[current_node] + edge_weight
            # check if the neighbor has already been visited
            if neighbor in visited:
                continue
            # check if the current neighbor is already in the shortest paths
            if neighbor not in shortest_paths or total_distance < shortest_paths[neighbor]:
                # add the neighbor to the shortest paths
                shortest_paths[neighbor] = total_distance
                # add the neighbor to the paths
                paths[neighbor] = paths[current_node] + [neighbor]
        # mark the current node as visited
        visited.add(current_node)
    # return an empty list if there is no path
    return []

4. Find the shortest path from node A to all other nodes in a weighted graph.

def dijkstra(graph, start):
    # create a set of nodes not yet evaluated
    unvisited_nodes = set(graph.nodes)
    # create a dictionary to hold the shortest path to each node
    shortest_paths = {node: float('inf') for node in graph.nodes}
    # set the distance from the start node to itself to 0
    shortest_paths[start] = 0
    # while there are nodes to evaluate
    while unvisited_nodes:
        # find the unvisited node with the smallest distance
        current_node, current_distance = sorted(
            [(node, shortest_paths[node]) for node in unvisited_nodes],
            key=lambda x: x[1])[0]
        # remove the current node from the unvisited nodes
        unvisited_nodes.remove(current_node)
        # for each neighbour of the current node
        for neighbour, distance in graph.edges[current_node].items():
            # if the distance to the neighbour is lower than the current
            # distance
            if distance + current_distance < shortest_paths[neighbour]:
                # update the distance to the neighbour
                shortest_paths[neighbour] = distance + current_distance
    return shortest_paths

Conclusion

You could use these codes explaining dijkstra algorithm.

Leave a Reply