迪杰斯特拉求两个城市的最短距离

迪杰斯特拉算法是一种用于求解最短路径问题的算法。它可以用来求解两个城市之间的最短距离。下面是一个使用迪杰斯特拉算法求解两个城市最短距离的示例：

假设有一个带权有向图，其中每个节点表示一个城市，每条边表示两个城市之间的道路，边的权重表示两个城市之间的距离。我们要求解从起始城市到目标城市的最短距离。

首先，我们需要初始化一些数据结构，包括一个距离数组dist和一个已访问数组visited。dist数组用于存储从起始城市到每个城市的最短距离，visited数组用于标记每个城市是否已经被访问过。

然后，我们将起始城市的最短距离设置为0，并将其标记为已访问。接下来，我们遍历起始城市的所有邻居城市，并更新它们的最短距离。如果更新后的最短距离小于原来的最短距离，则更新dist数组。

接着，我们从未访问的城市中选择一个距离最短的城市作为下一个要访问的城市，并将其标记为已访问。然后，我们再次遍历该城市的所有邻居城市，并更新它们的最短距离。

重复上述步骤，直到所有的城市都被访问过或者找到了目标城市。

最后，我们可以通过查询dist数组来获取起始城市到目标城市的最短距离。

下面是一个使用迪杰斯特拉算法求解两个城市最短距离的示例代码：

import sys

def dijkstra(graph, start, target):
    # 初始化距离数组
    dist = [sys.maxsize] * len(graph)
    dist[start] = 0

    # 初始化已访问数组
    visited = [False] * len(graph)

    # 循环遍历所有城市
    for _ in range(len(graph)):
        # 找到距离最短的城市
        min_dist = sys.maxsize
        min_dist_city = -1
        for i in range(len(graph)):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                min_dist_city = i

        # 标记该城市为已访问
        visited[min_dist_city] = True

        # 更新邻居城市的最短距离
        for i in range(len(graph)):
            if not visited[i] and graph[min_dist_city][i] != 0 and dist[min_dist_city] + graph[min_dist_city][i] < dist[i]:
                dist[i] = dist[min_dist_city] + graph[min_dist_city][i]

    return dist[target]

# 示例图的邻接矩阵表示
graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
]

start = 0
target = 4

shortest_distance = dijkstra(graph, start, target)
print("The shortest distance from city", start, "to city", target, "is", shortest_distance)

这段代码使用了邻接矩阵来表示图，其中0表示两个城市之间没有直接的道路。你可以根据实际情况修改图的表示方式。