[Python知识库]python迪杰斯特拉最短路径算法

def findCheapestPrice(n, flights, src):
    MAX = 1000000
    graph = [[MAX] * n for _ in range(n)]
    visited = [False] * n
    dist = [MAX] * n
    dist[src] = 0

    for u, v, w in flights:
        graph[u][v] = w
        if u == src:
            dist[v] = w

    visited[src] = True
    for _ in range(n - 1):
        min_v = MAX
        min_id = None
        for j in range(n):
            if not visited[j] and dist[j] < min_v:
                min_v = dist[j]
                min_id = j

        visited[min_id] = True
        for i in range(n):
            if not visited[i] and graph[min_id][i] != MAX and dist[min_id] + graph[min_id][i] < dist[i]:
                dist[i] = dist[min_id] + graph[min_id][i]

    return graph[0]


n = 4
flights = [[0,1,10],[1,2,10],[0,2,30], [1,3,5], [3,2,3]]
src= 0
dst =2
print(findCheapestPrice(n, flights, src))