python解决求最短路径、最短时间问题

对于一个求最短路径的经常遇到的问题，对于从某一个节点到其余全部节点所需要的最短时间的问题，可以使用广度优先搜索算法的思路来进行解决，这是一个广度优先搜索算法在二维空间的应用。

问题描述为给定一个节点总数为N和一个列表list，对于这个列表中的某一个元素，list[i]=[node1,node2,time]，这个列表元素表示的是从节点node1到节点node2所需要花费的时间长度是time值，而如果以一个节点K为起点，就对到达所有节点的时间至少需要多少时间求值。这里需要注意的就是list[i]这里面的边是单向的，就是从node1到node2之间的时间长度。

添加图片注释，不超过 140 字（可选）

如上图给定一个link，给定两个节点，输出的时间值是2

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

而如上的另外一个link以及两个值，输出的值是-1

添加图片注释，不超过 140 字（可选）

对于这个问题，如果说想要知道从节点K到所有节点至少需要花费多少时间，就需要求出节点K到每个节点的时间长度，然后从其中找出最大的值即可，这个问题就可以转化成一个求节点K到每个节点所需最短时间问题。如果使用一个列表来存储节点K到每个节点的最短时间长度，那通过判断某一节点作为中间节点能否使节点K到另外一个节点Q的时间长缩短来更新这个列表，并且由于K到Q最短时间长的更新可能导致整体的变化，所以就将节点Q进入队列中，并将其作为中间节点之后再更新定义的列表。

在实现过程中，主要是通过不断地以个节点为中间节点缩小节点K到其他各个节点的时间长度，若节点K到某一个节点时间长度减小，则就以该节点为中间节点更新节点K到其余各个节点的时间长度，在整个循环迭代中直到更新到最优。

使用python的代码实现如下：

from collections import deque
def ShortestPath(link,N,K):
    graph=[[float('inf') for _ in range(N)]for _ in range(N)]
    for d in link:
        x=d[0]-1
        y=d[1]-1
        graph[x][y]=d[2]
    for i in range(N):
        graph[i][i]=0 
    K2other=[float('inf') for _ in range(N)]
    K2other[K-1]=0
    queue=deque([K-1])
    while queue:
        current=queue.popleft()
        for i in range(N):
            if K2other[current]+graph[current][i]<K2other[i]:
                K2other[i]=K2other[current]+graph[current][i]
                queue.append(i)
    if float('inf') in K2other:
        return -1
    return max(K2other)