Finding Shortest Path in Weighted Graphs with Dijkstra#s Algorithm

This function finds the shortest path from a source to a target in a weighted graph using Dijkstra's algorithm.

Technology Stack : graph-tool

Code Type : Function

Code Difficulty : Intermediate

                
                    
def find_shortest_path(graph, source, target):
    """
    Find the shortest path in a weighted graph using Dijkstra's algorithm.

    Parameters:
    graph (graph-tool.Graph): The graph object.
    source (int): The source vertex.
    target (int): The target vertex.

    Returns:
    list: The shortest path from source to target.
    """
    # Initialize the distance dictionary with infinite distances
    distances = {vertex: float('infinity') for vertex in graph.vertices()}
    distances[source] = 0
    
    # Priority queue to store vertices and their distances
    priority_queue = [(0, source)]
    
    while priority_queue:
        # Get the vertex with the smallest distance
        current_distance, current_vertex = min(priority_queue)
        priority_queue.remove((current_distance, current_vertex))
        
        # If the target is reached, return the path
        if current_vertex == target:
            path = [current_vertex]
            while current_vertex != source:
                current_vertex = graph.out_neighbors(current_vertex)[distances[current_vertex]]
                path.append(current_vertex)
            return path[::-1]
        
        # Update the distances to the neighbors
        for neighbor, weight in zip(graph.out_neighbors(current_vertex), graph.out_edges(current_vertex)[2]):
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                priority_queue.append((distance, neighbor))
    
    return None