dijkstra python
时间: 2023-06-21 17:24:16 浏览: 47
Dijkstra's algorithm is a shortest path algorithm used to find the shortest path between two nodes in a graph. Here is an implementation of Dijkstra's algorithm in Python:
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
```
Here, `graph` is a dictionary where the keys are the nodes of the graph and the values are dictionaries of the neighbors and their corresponding weights. `start` is the starting node for the algorithm.
The function initializes a `distances` dictionary with all nodes having a distance of infinity except for the `start` node, which has a distance of 0. It then initializes a `queue` with a tuple containing the distance and the starting node.
The algorithm then enters a loop where it pops the node with the smallest distance from the queue. It then checks if its distance is smaller than the previously calculated distance for that node. If it is, it updates the distance for that node and adds its neighbors to the queue with their corresponding distances.
Finally, the function returns the `distances` dictionary with the shortest distances from the `start` node to all other nodes in the graph.