python实现有向图单源最短路径迪杰斯特拉 算法

您好！要实现有向图的单源最短路径迪杰斯特拉算法，可以按照以下步骤进行：

1. 创建一个表示有向图的数据结构，可以使用邻接矩阵或邻接表来存储图的信息。这里我们使用邻接表进行演示。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
    
    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

2. 实现迪杰斯特拉算法的函数，接受图和起始节点作为参数，并返回从起始节点到所有其他节点的最短路径长度。

import sys

def dijkstra(graph, src):
    dist = [sys.maxsize] * graph.V
    dist[src] = 0
    visited = [False] * graph.V

    for _ in range(graph.V):
        u = min_distance(dist, visited)
        visited[u] = True

        for v, w in graph.graph[u]:
            if not visited[v] and dist[u] != sys.maxsize and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    return dist


def min_distance(dist, visited):
    min_dist = sys.maxsize
    min_index = -1

    for v in range(len(dist)):
        if not visited[v] and dist[v] < min_dist:
            min_dist = dist[v]
            min_index = v

    return min_index

3. 使用上述代码，创建一个图并调用迪杰斯特拉算法函数来计算最短路径。

g = Graph(5)
g.add_edge(0, 1, 6)
g.add_edge(0, 3, 1)
g.add_edge(1, 2, 5)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(2, 4, 1)
g.add_edge(4, 3, 1)

src = 0
distances = dijkstra(g, src)

print("最短路径长度:")
for i in range(g.V):
    print(f"从节点 {src} 到节点 {i} 的最短路径长度为: {distances[i]}")

这样，您就可以使用迪杰斯特拉算法找到有向图中从给定起始节点到所有其他节点的最短路径长度了。请注意，上述代码中使用了 sys.maxsize 表示无穷大，您可以根据自己的需求进行调整。希望对您有所帮助！如有任何问题，请随时提问。