gistlib - find shortest path in map in python

To find the shortest path in a map, we can use graph theory and the Dijkstra algorithm. In graph theory, a map is represented as a graph where the nodes represent the locations on the map, and the edges represent the roads or paths connecting the locations.

To use Dijkstra's algorithm to find the shortest path from a starting point to an endpoint, we need to construct the graph and initialize the algorithm with the starting node. Here is an implementation of this algorithm in Python:


main.py
import heapq

def shortest_path(graph, start, end):
    # Keep track of the shortest distance to each node.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Keep track of the shortest path to each node.
    paths = {start: []}
    
    # Use a heap to keep track of the nodes with the smallest tentative distance.
    heap = [(0, start)]
    
    while heap:
        # Get the node with the smallest tentative distance.
        (distance, current_node) = heapq.heappop(heap)
        
        # If we have already found a shorter path to this node, skip it.
        if distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            # Calculate the tentative distance to this neighbor node.
            tentative_distance = distance + weight
            
            # If this path is shorter than the current shortest path to the neighbor, update it.
            if tentative_distance < distances[neighbor]:
                distances[neighbor] = tentative_distance
                paths[neighbor] = paths[current_node] + [current_node]
                # Add this node to the heap to explore it later.
                heapq.heappush(heap, (tentative_distance, neighbor))
    
    # Return the shortest path and its length.
    shortest_path = paths[end] + [end]
    path_length = distances[end]
    
    return shortest_path, path_length
1454 chars
38 lines

The graph input should be a dictionary representing the graph, where the keys are the nodes and the values are dictionaries containing the neighbors and their corresponding edge weights.

For example, if we have a map with the following locations and distances between them:


main.py
A <-> B <-> C <-> D <-> E
26 chars
2 lines

We can represent it as a graph with the following dictionary:


main.py
graph = {
    'A': {'B': 1},
    'B': {'A': 1, 'C': 2},
    'C': {'B': 2, 'D': 1},
    'D': {'C': 1, 'E': 3},
    'E': {'D': 3}
}
130 chars
8 lines

To find the shortest path from node A to node E, we can call the shortest_path function like this:


main.py
shortest_path, path_length = shortest_path(graph, 'A', 'E')
print(shortest_path)  # ['A', 'B', 'C', 'D', 'E']
print(path_length)    # 7
136 chars
4 lines

find shortest path in map in python

similar python code snippets

related categories