find shortest path in python

To find the shortest path between two nodes in a graph, we can use Dijkstra's algorithm. Here's a Python implementation of the algorithm using a priority queue data structure:


main.py
import heapq

def dijkstra(graph, start):
    """
    Finds the shortest path from start to all other nodes in the graph.
    :param graph: a dictionary representing the graph
    :param start: the starting node
    :return: a dictionary of shortest distances from start to all other nodes
    """
    # initialize distances to all nodes as infinite except for start node
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # initialize priority queue with start node and its distance
    pq = [(0, start)]

    while pq:
        # pop node with smallest distance from start
        (dist, curr_node) = heapq.heappop(pq)

        # update distances of neighbors
        for neighbor, neighbor_dist in graph[curr_node].items():
            distance = dist + neighbor_dist
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances
977 chars
29 lines

The input graph should be a dictionary where the keys are the nodes in the graph and the values are also dictionaries that contain the neighbor nodes and their corresponding distances. For example:


main.py
graph = {
    'A': {'B': 2, 'C': 1},
    'B': {'A': 2, 'C': 4, 'D': 1},
    'C': {'A': 1, 'B': 4, 'D': 3},
    'D': {'B': 1, 'C': 3}
}
135 chars
7 lines

To find the shortest path from node A to node D, we can call the dijkstra function with graph and start='A'. The result would be:


main.py
{'A': 0, 'B': 2, 'C': 1, 'D': 3}
33 chars
2 lines

This means that the shortest distance from A to D is 3, and the path is A -> C -> D.

similar python code snippets

identify a eulerian cycle in python in python

define a function to create a eulerian cycle in python

create a 2 by 4 graph in matplotlib in python

create a graph neural network in pytorch in python

calculate the adamic–adar index in python

define a function that returns whether a graph is eulerian or not in python

breadth first search in python

send an email in python

find urls in a string in python

open a file in python

related categories