最短路径算法

• Dijkstra算法
• Floyd算法

Dijkstra算法

基本思想：每次找到离源点（如1号结点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

解决单源最短路径

理论

该算法包含四个步骤：

1. 找出“最便宜”并没有访问过的节点，既在最短时间内可以到达的节点

   这里应该是指距离开始节点最接近的节点

2. 更新该节点的邻居节点的开销

   既 distance(起点，当前节点) + distance(当前节点，它的邻居节点) = distance(起点，邻居节点)

3. 重复这个过程，直到对图中的每个节点都这样做了。

4. 计算最终路径。

图解

初始状态：

用一个数组记录各个节点到起点的距离，除起点设为0外，其他全部为无穷大。

第一步，找出最便宜的节点：

由起点距离起点最近，故起点为找到的节点

第二步，计算经最便宜的节点前往其各个邻居所需的时间：

通过起点前往A，B的时间为：

邻居节点	距离
A	6
B	2

此时，起点距离B，A的距离分别为2,6。在数组中记录

dis[起点] = 0, dis[A] = 6, dis[B] = 2

第三步，重复以上两步

• 找出未访问过且最便宜的节点

  此时为B

• 计算经最便宜节点前往其各个邻居所需的时间

  B的邻居有：A，终点

  邻居节点	新的距离
  A	dis(起点,B)+dis(B,A) < dis(起点,A)，故更新为5
  终点	dis(起点,B)+dis(B,终点)<dis(起点，终点)，故更新为7

  此时，距离数组更新如下：

  dis[起点] = 0, dis[A] = 5, dis[B] = 2, dis[终点]=7

  此时，已经访问起点，和B，还有两个节点没有访问

第四步，重复以上两步

• 找出未访问过且最便宜的节点

  此时为A

• 计算经最便宜节点前往其各个邻居所需的时间：

  A的邻居有：B，终点

  邻居节点	距离
  B	dis(起点,A)+dis(A,B) > dis(起点,B)，不更新，其实这步可以不要，因为前面已经证明B小于A
  终点	dis(起点,A)+dis(A,终点)<dis(起点，终点)，故更新为6

  此时，距离数组更新如下：

  dis[起点] = 0, dis[A] = 5, dis[B] = 2, dis[终点]=6

  此时，已经访问起点，A 和B，还有1个节点没有访问

第五步，重复以上两步

在这里会退出。

代码

cost = [[float("inf") for _ in range(6)] for _ in range(6)]
cost[0][1], cost[1][0] = 1, 1
cost[0][2], cost[2][0] = 2, 2
cost[0][3], cost[3][0] = 7, 7
cost[1][2], cost[2][1] = 2, 2
cost[1][4], cost[4][1] = 5, 5
cost[1][5], cost[5][1] = 4, 4
cost[2][3], cost[3][2] = 4, 4
cost[2][4], cost[4][2] = 4, 4
cost[3][4], cost[4][3] = 6, 6
cost[4][5], cost[5][4] = 3, 3
def test5(start_point,jam_point,jam_value):
    V = 6
    used = [False for _ in range(V)] # 标记节点是否被访问过
    distance = [float('inf') for _ in range(V)] # # 距离数组：distance[i]表示从源点s到ｉ的最短距离，distance[s]=0
    paths = [-1] * V
    # 拥堵系数
    for i in range(V):
        for j in range(V):
            if i == jam_point or j == jam_point:
                cost[i][j] += jam_value
    distance[start_point] = 0 # 起点的距离标为0
    while True:
        v = -1 # v在这里相当于是一个哨兵，对包含起点s做统一处理！
        # 步骤2
        for u in range(V):
            # 从未使用过的顶点中选择一个距离最小的顶点
            if not used[u] and (v==-1 or distance[u] <distance[v]):
                v = u
        print("v:",v)
        if v == -1:
                # 说明所有定点维护到S中
            break
            
        used[v] = True # 加入到S

        # 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，
        # 从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
        for u in range(V):
            if not used[u] and distance[v] + cost[v][u] < distance[u]:
                distance[u] = distance[v]+cost[v][u]
                paths[u] = v # 相当于节点u有中途节点
def print_path(sec,n,paths,dis):
    '''
    sec表示出发节点，n表示节点总数
    '''
    i = 0
    j = 0
    q = list()
    for i in range(0,n):
        j = i
        while paths[j] != -1: # 如果j有中图节点
            q.append(j) # 添加当前节点

            j = paths[j] # 取当前节点的中转节点
        q.append(j)
        print('{}=>{}, length:{}, path: {},'.format(sec,i,dis[i],sec),end=' ')

        while len(q) != 0:
            print(q.pop(),end=' ')
        print()

参考文档：

• 算法图解
• 代码

例题

美团外卖是知名的外卖平台，现在有一名新入职的外卖小哥。请你给他写一段程序根据外卖地图和交通拥堵情况，告诉他从“配送点”V0，到各个目的地的最短配送距离。其中拥堵程度可以与路径参数直接相加，例如：V0点拥堵，拥堵系数是2，那么在地图上V0点的3条线路的参数都要加2，由原来的1、2、7变为3、4、9再进行。

Floyd算法

所有点对的最短路径

从出发地到目的地的过程中，我们并不是一下子就到达目的地，而是要经过很多的中转站来帮助我们一步一步地到达目的地。

参考链接：https://blog.csdn.net/Lwenjiyou_/article/details/79548577

代码

N = 4
M = float('inf')
edge = np._mat.mat(
    [
        [0, 2, 6, 4],
        [M, 0, 3, M],
        [7, M, 0, 12],
        [5, M, 1, 0]
    ]
)
A = edge.copy()
path = np.zeros((N,N)) - 1 # 用于保存两点之间需要中转的点

def Floyd():
    # TODO 路径初始化，每个节点对起始路径为自己
    for i in range(N):
        for j in range(N):
            if edge[i,j] != M and edge[i,j]!=0:
                path[i][j] = i
    # print(path)
    print("init")

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i,k] + A[k,j] < A[i,j]:
                    A[i,j] = A[i,k] + A[k,j]
                    path[i,j] = path[k,j]
                
    print("最短距离:")
    print(A)
    print("路径：")
    q = [] # 存储中间节点
    while int(paths[start_point,end_point]) != -1:
        t= int(paths[start_point,end_point])
        if t == start_point: break
        q.append(t)
        start_point = t
    print(q)

---

NC158 单源最短路

描述

在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1

图中可能有重边，无自环。

解法：迪杰斯特拉

class Solution:
    def findShortestPath(self , n , m , graph ):
        # write code here
        adjs = [[float("inf") for _ in range(n)] for _ in range(n)]
        for edges in graph:
#             print(edges)
            u,v,w = edges[0],edges[1],edges[2]
            adjs[u-1][v-1] = min(adjs[u-1][v-1],w)
        used = [False] * n # 标记是否访问过
        distance = [float("inf") for _ in range(n)] # 起点距离各点的距离数组
        paths = [-1] * n # 用于记录路径
        distance[0] = 0 # 起点的距离为0
        while True:
            v = -1 # 相当于哨兵
            # 从未使用过的节点选择一个最小的
            for u in range(n):
                if not used[u] and (v== -1 or distance[u]<distance[v]):
                    v = u
            if v == -1:
                break # 说明所有顶点都已访问过
            
            used[v] = True # 标记已访问
            
            # 更新U中各个顶点到起点s的记录
            for u in range(n):
                if not used[u] and distance[v] + adjs[v][u] < distance[u]:
                    distance[u] = distance[v]+adjs[v][u]
#         print(distance)
#         print(adjs[0][n-1])
        return distance[n-1]

解法：佛洛依德算法

超时

class Solution:
    def findShortestPath(self , n , m , graph ):
        # write code here
        adjs = [[float("inf") for _ in range(n)] for _ in range(n)]
        for edges in graph:
#             print(edges)
            u,v,w = edges[0],edges[1],edges[2]
            adjs[u-1][v-1] = min(adjs[u-1][v-1],w)
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if adjs[i][k] + adjs[k][j] < adjs[i][j]:
                        adjs[i][j] = adjs[i][k] + adjs[k][j]
        return adjs[0][n-1]