图（5）最短路径树

骑猪看日落 2023-07-06 06:25 12阅读 0赞

1、什么是最短路径  
这里讨论的是带权有向图和带权无向图，在这类图中一个顶点到其他顶点可能有路径，可能没有路径，也可能有多条不同的路径，怎样找到一条最好的路径呢，这就是本节要讨论的最短路径问题。  
定义：  
在图中：

*  从顶点v到 v ‘ v^\` v‘的各个边的长度之和就称为该路径的长度。
 *  从v到 v ‘ v^\` v‘的所有长度中最短的路径就是v到 v ‘ v^\` v‘的最短路径，最短路径记为dist(v,v\`)  
    在介绍之前我们要先明确几个概念 （1）最小生成树（2）最短路径树（3）最短路径  
    （1）最小生成树  
    将最少的边集将一个图连成任意2点可达，并且这个边集的总长度最小。保证整个拓扑图的所有路径之和最小。通常用Prim算法和kruskal算法求解。  
    （最小生成树是指图中一点到其他所有顶点的总和最小）  
    （2）最短路径树  
    最短路径树是指，图中一点到其他所有点的最短路径构成的树  
    （3）最短路径  
    最短路径是指图中任意两点形成的最短路径  
      
    2、最短路径树  
    最短路径树，又称为单源最短路径树，是指从图中一个顶点出发，到其他任意顶点的最短路径构成树的集合  
    算法概要：  
    1、将图中顶点分为两个集合，当时已知的最短路径的集合U,和尚不知道的最短路径的集合V-U  
    2、在集合U中放入顶点v0，v0到v0的距离的为0  
    3、对V-U的每个顶点v，如果存在v和v0相连的话，则将其v0-v的权值w设为已知的权值w，否则设为None.  
    不断重复：
 *  从V-U中选出当时已知的最段路径的顶点 v m i n v\_\{min\} vmin加入U,
 *  由于 v m i n v\_\{min\} vmin的加入，V-U中的已知的最短路径可能发生改变，如果从v0到 v m i n v\_\{min\} vmin到 v ‘ v\` v‘的路径比以前已知的路径的更短，则更新 v ‘ v\` v‘ 的最短路径的距离记录，保证能继续在V-U中挑选顶点。

看完了，还是有点晕还是来看例子吧。

时间复杂度：O(Elog(v))  
我们以一个例子来看看dijkstra的具体实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20190504172034513.png]  
下面将介绍最短路径树的矩阵生成方式：

matrix=[[0,5,11,5,0,0,0],
            [5,0,0,3,9,0,7],
            [11,0,0,7,0,6,0],
            [5,3,7,0,0,0,20],
            [0,9,0,0,0,0,7],
            [0,0,6,0,0,0,8],
            [0,7,0,20,7,8,0]]
    n=len(matrix[0]) #顶点数
    record=[False for i in range(n)]
    dict1={
        } #利用字典充当一个队列，每次从中选择当前的最短路径,字典每次记录
    #所有的最短路径树，并从中弹出最短路径
    dict2={
        } #记录最短路径树各个边对应的路径顺序
    for i in range(n):
        dict1[i]=None
        dict2[i]=[]
    #初始化顶点
    i=0
    dict1[i]=0
    dict2[i].append([0,0])
    record_arr=[]
    while True:
        print('dict1:',dict1)
        print('dict2:',dict2)
        if sum(record)==n:
            break
        list1=sorted(dict1.items(),key=lambda x:x[0],reverse=True)    
        edge=list1.pop()
        dict1=dict(list1)
        start=edge[0]
        w1=edge[1]
        record[start]=True
        dict2[start]=edge
        i=start
        arr1=[]
        for j in range(n):
            if matrix[i][j]!=0 and record[j]==False:
               arr1.append([i,j,matrix[i][j]]) 
        #用最短边去更新dict1
        for edge in arr1:
            start,end,w=edge[0],edge[1],edge[2]
            if record[end]==False:
                if dict1[end]==None:
                    dict1[end]=w+w1
                else:
                    dict1[end]=min(dict1[end],w1+w)
    dict1: {
        0: 0, 1: None, 2: None, 3: None, 4: None, 5: None, 6: None}
    dict2: {
        0: [[0, 0]], 1: [], 2: [], 3: [], 4: [], 5: [], 6: []}
    dict1: {
        6: None, 5: None, 4: None, 3: 5, 2: 11, 1: 5}
    dict2: {
        0: (0, 0), 1: [], 2: [], 3: [], 4: [], 5: [], 6: []}
    dict1: {
        6: 12, 5: None, 4: 14, 3: 5, 2: 11}
    dict2: {
        0: (0, 0), 1: (1, 5), 2: [], 3: [], 4: [], 5: [], 6: []}
    dict1: {
        6: 12, 5: 17, 4: 14, 3: 5}
    dict2: {
        0: (0, 0), 1: (1, 5), 2: (2, 11), 3: [], 4: [], 5: [], 6: []}
    dict1: {
        6: 12, 5: 17, 4: 14}
    dict2: {
        0: (0, 0), 1: (1, 5), 2: (2, 11), 3: (3, 5), 4: [], 5: [], 6: []}
    dict1: {
        6: 12, 5: 17}
    dict2: {
        0: (0, 0), 1: (1, 5), 2: (2, 11), 3: (3, 5), 4: (4, 14), 5: [], 6: []}
    dict1: {
        6: 12}
    dict2: {
        0: (0, 0), 1: (1, 5), 2: (2, 11), 3: (3, 5), 4: (4, 14), 5: (5, 17), 6: []}
    dict1: {
        }
    dict2: {
        0: (0, 0), 1: (1, 5), 2: (2, 11), 3: (3, 5), 4: (4, 14), 5: (5, 17), 6: (6, 12)}

dict1为一个优先队列不断更新与弹出当前最短路径  
dict2为最短记录树的记录

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190504171827789.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190504171917634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190504171951414.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ==,size_16,color_FFFFFF,t_70
[20190504172034513.png]: https://img-blog.csdnimg.cn/20190504172034513.png