Dijkstra python
时间: 2023-10-17 09:37:38 浏览: 42
Dijkstra's algorithm is a graph search algorithm used to find the shortest path between nodes in a graph. Here is an implementation in Python:
```python
import sys
def dijkstra(graph, start):
# Initialize the distance dictionary with infinity for all nodes except the start node
distance = {node: sys.maxsize for node in graph}
distance[start] = 0
# Set of visited nodes
visited = set()
while len(visited) != len(graph):
# Find the node with the minimum distance
min_node = None
min_distance = sys.maxsize
for node in graph:
if node not in visited and distance[node] < min_distance:
min_node = node
min_distance = distance[node]
# Mark the current node as visited
visited.add(min_node)
# Update the distances of the neighboring nodes
for neighbor, weight in graph[min_node].items():
new_distance = distance[min_node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
return distance
# Example usage
graph = {
'A': {'B': 5, 'C': 3},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 3, 'B': 1, 'D': 2},
'D': {'B': 3, 'C': 2}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print(f"Shortest distances from node {start_node}:")
for node, distance in distances.items():
print(f"To node {node}: {distance}")
```
This implementation uses a priority queue to efficiently select the node with the minimum distance at each step. It iteratively updates the distances of nodes until all nodes have been visited. The result is a dictionary that maps each node to its shortest distance from the start node.