迪杰斯特拉最短路径代码
时间: 2023-07-10 21:35:37 浏览: 56
以下是使用 Python 实现的迪杰斯特拉最短路径算法的代码:
```python
import heapq
def dijkstra(graph, src):
dist = {node: float('inf') for node in graph} # 到源节点的距离
dist[src] = 0
pq = [(0, src)] # 优先队列,按距离排序
while pq:
(d, u) = heapq.heappop(pq)
if d > dist[u]:
continue
for v, weight in graph[u].items():
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return dist
```
其中,`graph` 是图的邻接表表示,`src` 是源节点。函数返回一个字典,其中键为节点,值为到源节点的最短距离。
相关问题
迪杰斯特拉最短路径算法【图】
迪杰斯特拉最短路径算法是一种解决有权图中单源最短路径问题的算法。它采用贪心策略,以起始点为中心向外层层扩展,直到扩展到终点为止。该算法主要特点是将图中的节点集分为最短路径计算完成的节点集S和未计算完成的节点集T,每次将从T中挑选V0->Vt最小的节点Vt加入S,并更新V0经由Vt到T中剩余节点的更短距离,直到T中的节点全部加入S中。迪杰斯特拉算法只支持非负权图,它计算的是单源最短路径,即单个源点到剩余节点的最短路径,时间复杂度为O(n²)。
以下是迪杰斯特拉最短路径算法的具体步骤:
1. 初始化:将起始点s加入S集合,将与s直接相连的节点的距离加入dis数组,将其余节点的距离设为无穷大。
2. 重复执行以下步骤,直到T集合为空:
a. 从dis数组中选择值最小的节点v,将其加入S集合。
b. 更新dis数组:对于T集合中的每个节点w,如果存在一条从v到w的边,则计算出v到w的距离,并将其与原有距离进行比较,如果更小则更新dis数组中w的值。
3. 得到起始点s到各个节点的最短路径。
以下是Python实现迪杰斯特拉最短路径算法的代码示例:
```python
import sys
def dijkstra(graph, start):
# 初始化
dis = {node: sys.maxsize for node in graph} # 距离数组
dis[start] = 0
S = set() # 最短路径节点集合
T = set(graph.keys()) # 未计算最短路径节点集合
while T:
# 选择距离起点最近的节点
v = min(T, key=lambda node: dis[node])
S.add(v)
T.remove(v)
# 更新距离数组
for w in graph[v]:
if dis[w] > dis[v] + graph[v][w]:
dis[w] = dis[v] + graph[v][w]
return dis
# 测试
graph = {
'A': {'B': 5, 'C': 1},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
'E': {'C': 8, 'D': 3},
'F': {'D': 6}
}
start = 'A'
print(dijkstra(graph, start)) # 输出:{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7, 'F': 10}
```
迪杰斯特拉最短路径完整代码matlab
以下是迪杰斯特拉算法的完整代码,使用Matlab编写:
```matlab
function [distances, previous] = dijkstra(adjacency_matrix, start_node)
% DIJKSTRA Calculates the shortest path between nodes in a graph using the Dijkstra algorithm
% [distances, previous] = DIJKSTRA(adjacency_matrix, start_node) returns the distances
% from the start_node to each node in the graph and the previous node for each node on the
% shortest path from start_node to that node.
%
% adjacency_matrix is a square matrix representing the weighted edges of the graph
% start_node is the index of the starting node
%
% Example usage:
%
% >> adjacency_matrix = [0 7 Inf 5; 7 0 8 9; Inf 8 0 Inf; 5 9 Inf 0]
% >> [distances, previous] = dijkstra(adjacency_matrix, 1)
% distances =
% 0 7 15 5
% previous =
% 0 1 2 1
% Initialize variables
num_nodes = size(adjacency_matrix, 1);
visited = false(1, num_nodes);
distances = Inf(1, num_nodes);
previous = zeros(1, num_nodes);
% Set the distance to the start node to 0
distances(start_node) = 0;
% Loop through all nodes in the graph
for i = 1:num_nodes
% Find the node with the smallest distance that has not been visited yet
[min_distance, current_node] = min(distances(~visited));
% If all remaining nodes are inaccessible, break out of the loop
if isempty(current_node)
break;
end
% Mark the current node as visited
visited(current_node) = true;
% Loop through all neighbors of the current node
for j = 1:num_nodes
if adjacency_matrix(current_node, j) ~= Inf && ~visited(j)
% Calculate the distance to the neighbor through the current node
distance = min_distance + adjacency_matrix(current_node, j);
% If the distance is shorter than the current shortest distance to the neighbor, update it
if distance < distances(j)
distances(j) = distance;
previous(j) = current_node;
end
end
end
end
end
```
使用方法:
1. 定义一个邻接矩阵,其中 Inf 表示两个节点之间没有边连接
2. 调用 dijkstra 函数,传递邻接矩阵和起始节点的索引作为参数
3. 函数将返回一个距离数组和前驱节点数组,其中距离数组表示从起始节点到每个节点的最短距离,前驱节点数组表示从起始节点到每个节点的最短路径上每个节点的前一个节点的索引,如果不存在前驱节点,则为0