【最短路算法】dijkstra，SPFA和folyd

在了解本知识点之前，首先要了解图的建立，也就是邻接表和邻接矩阵。

邻接矩阵适用于稠密图

邻接表适用于稀疏图

目录

单源最短路问题

dijkstra算法

SPFA算法

folyd算法

最小生成树

拓扑排序

关键路径

---

单源最短路问题

首先我们要了解什么是单源最短路，什么是多源最短路：

单源最短路是指具体的起点到终点的最短路

多源最短路是指任意两点间的最短路

 

对于该图A到C的最短路问题，如果我们用BFS进行求解，如下图

 我们因为用队列的缘故，在D出栈后就结束BFS了。然而我们求得的A到C的最短路答案是5

很显然最短应该是3

 这个时候，BFS的问题就出来了，因此我们不能用BFS来求解带权图（或是权值都相等的图）；

此时我们可以用dijkstra求解，当然我们用DFS也可以求解
 

dijkstra算法

特点：每个点只访问一次，可以用于有向图

注意：dijkstra算法只能适用于非负权图（或是全是负权值的图）

顺序红黄绿

用 dijkstra算法求解的话，A到B的最短距离是1，实际上是-3，即A->C->D->B

dijkstra算法中内含贪心思想

实现dijkstra算法解决1到n的最短路

n,m=map(int,input().split())
mg=[[float('inf')]*(n+1) for i in range(n+1)]
for i in range(m):
    new,next,v=map(int,input().split())
    mg[new][next]=v
    mg[next][new] = v
vis=[0]*(n+1)
dis=[float('inf')]*(n+1)
def dijkstra(start):
    for i in range(1,n+1):
        dis[i]=mg[start][i]#更新起点start到所有点的边的值
    vis[start]=1#对起点start标记
 
    for i in range(n):#循环n次，每次标记一个图中符合条件且未被标记的点，故标记所有点要循环n次
        min_dis=float('inf')#存储最小值
        min_index=-1#储存最小值的点序号
        for j in range(1,n+1):#遍历所有点
            if vis[j]!=1 and dis[j]#找到未被标记且距离起点start最短的点
                min_dis=dis[j]#该点距离
                min_index=j#该点序号
        #从该最短点出发
        for j in range(1,n+1):
            if vis[j]!=1 and dis[min_index]+mg[min_index][j]#更新最短点能到达的点到起点start的距离
                dis[j]=dis[min_index]+mg[min_index][j]
        vis[min_index]=1#标记最短点
dijkstra(1)#起点序号
print(dis[n])#终点序号
 
# 3 3
# 1 2 5
# 2 3 5
# 3 1 2
#
# 2

邻接矩阵版

适用于点数不大(例如V不超过1000)的情况,相对好写。代码如下:

n,m,s,g=map(int,input().split())#输入顶点数,边数，起点和终点
mg=[[float('inf')]*n for i in range(n)]
d=[float('inf')]*n#地点到达各点的最短路径长度
vis=[0]*n#标记数组
pre=[-1]*n#记录最短路径本身，pre[v]表示从起点到顶点v的最短路径上v的前一个顶点
for i in range(m):
    u, v, dis = map(int, input().split())
    mg[u][v]=dis#单向边添加
    #mg[v][u] = dis#无向边，双向添加
 
def Dijkstra(s):#s为起点
    d[s]=0#起点到自身的距离为0
    for i in range(n):#有n个点就有n次操作，故循环n次
        u=-1#u为从起点到所有为被标记的点的最短距离所对应的点，即步骤一
        mini=float('inf')#存储最小值以便找到最小值
        for j in range(n):#循环每个点
            if vis[j]==0 and d[j]#找到未被访问的顶点中距离起点最小的，即步骤一
                u=j
                mini=d[j]
        #如果找不到小于INF的d[u]，说明剩下的顶点和起点不联通
        #print(u)
        if u==-1:
            return
        #如果找到，标记u
        vis[u]=1
        for v in range(n):#从u开始遍历每个点，即步骤二
            if vis[v]==0 and d[u]+mg[u][v]
                d[v]=d[u]+mg[u][v]#优化d[v]
                pre[v] = u  # 记录v的前驱顶点是u
 
Dijkstra(s)
print(d[g])  # 起点到指定顶点
print(*d)  # 起点到所有顶点
#l=[]
def DFS(u):#输入起点和终点递归出最短路径,从g开始
    if u==s:#等于起点时输出，
        print(s,end='->')
        #l.append(s)
        return
    DFS(pre[u])#g的前一个点
    #l.append(g)
    if u==g:
        print(u,end=' ')
    else:
        print(u,end='->')#起点输出完后输出起点后的带点
DFS(g)
#print(*l)
 
 
# 6 8 0 5
# 0 1 1
# 0 3 4
# 0 4 4
# 1 3 2
# 2 5 1
# 3 2 2
# 3 4 3
# 4 5 3
 
# 6
# 0 1 5 3 4 6
# 0->1->3->2->5

邻接表版

class Node:
    def __int__(self,v,dis):#v为边的目标顶点，dis为边权
        self.v=v
        self.dis=dis
 
n,m,s,g=map(int,input().split())#输入顶点数,边数，起点和终点
G=[[] for i in range(n)]#图G，G[u]存放从顶点u出发可以到达的所有顶点
vis=[0]*n
d=[float('inf')]*n
pre=[0]*n
def add(u,v,dis):#单向边添加
    node=Node()
    node.v=v
    node.dis=dis
    G[u].append(node)
 
def add2(u,v,dis):#无向边，双向添加
    add(u,v,dis)
    add(v, u, dis)
 
def Dijkstra(s):
    d[s]=0
    for i in range(n):
        u=-1
        mini=float('inf')
        for j in range(n):
            if vis[j]==0 and d[j]
                u=j
                mini=d[j]
 
        if u==-1:
            return
        vis[u]=1
        #只有下面这个for与邻接矩阵的写法不同
        size=len(G[u])
        for j in range(size):#遍历G[u]，即所有和u直接相连的所有边
            v=G[u][j].v
            if vis[v]==0 and d[u]+G[u][j].dis
                d[v]=d[u]+G[u][j].dis
                pre[v]=u
def DFS(u):
    if u==s:
        print(s,end='->')
        return
    DFS(pre[u])
    if u==g:
        print(u,end=' ')
    else:
        print(u,end='->')
 
if __name__ == '__main__':
    for i in range(m):
        u,v,dis=map(int,input().split())
        add(u, v, dis)
        #add2(u, v, dis)
    Dijkstra(s)
    print(d[g])#起点到指定顶点
    print(*d)#起点到所有顶点
    DFS(g)
 
# 6 8 0 5
# 0 1 1
# 0 3 4
# 0 4 4
# 1 3 2
# 2 5 1
# 3 2 2
# 3 4 3
# 4 5 3
# 6
# 0 1 5 3 4 6
# 0->1->3->2->5 
 

SPFA算法

特点：每个点可以访问多次（入栈多次）

注意：无法解决有负环的图

向栈加入点时，如果该点在队列里，则无需再次加入。

入栈顺序对结果没影响

解决带负权图（带负权图不可能为无向图），在稀疏图上的速度要快于dijkstra，故即使是不带负权的稀疏图也推荐使用SPFA算法

folyd算法

Floyd 算法（读者可以将其读作“弗洛伊德算法”）用来解决全源最短路问题，即对给定的图G(V,E),求任意两点u, v之间的最短路径长度,时间复杂度是O(n2)。由于n3的复杂度决定了顶点数n的限制约在200以内,因此使用邻接矩阵来实现Floyd算法是非常合适且方便的。
步骤：
建图

n,m,K=map(int,input().split())
a=[[float('inf') for i in range(n+1)]for j in range(n+1)]
 
for i in range(n+1):
    for j in range(n+1):
        if i==j:
            a[i][j]=0
for i in range(m):
    x,y,z=map(int,input().split())
    a[x][y]=min(a[x][y],z)

三循环

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if k!=i and k!=j:
                a[i][j]=min(a[i][j],a[i][k]+a[k][j])

求解

for i in range(K):
    x,y=map(int,input().split())
    if a[x][y]==float('inf'):
        print('impossible')
    else:
        print(a[x][y])

对 Floyd 算法来说，需要注意的是：不能将最外层的 k 循环放到内层（即产生 i->j->k 的三重循环），这会导致最后结果出错。理由是：如果当较后访问的 dis[u][v]有了优化之后，前面访问的dis[i][j]会因为已经被访问而无法获得进一步优化(这里i、j先于 u、v进行访问)。

如第一次循环i=1，j=2，假设选出最优解k=4，1-4-2的最优解已经得出，但是在后面求i=1，j=4时的得到最优解1-3-4，则之前1到2的最优解错误，最优解应为1-3-4-2，但是已经无法修改。

最小生成树

最小生成树（Minimum Spanning Tree，MST)是在一个给定的无向图 G(V,E)中求一棵树 T，使得这棵树拥有图 G 中的所有顶点，且所有边都是来自图 G 中的边，并且满足整棵树的边权之和最小。

最小生成树有 3 个性质需要掌握：

① 最小生成树是树，因此其边数等于顶点数减1，且树内一定不会有环。

② 对给定的图G(V,E),其最小生成树可以不唯一,但其边权之和一定是唯一的。

③ 由于最小生成树是在无向图上生成的，因此其根结点可以是这棵树上的任意一个结点。于是，如果题目中涉及最小生成树本身的输出，为了让最小生成树唯一，一般都会直接给出根结点，读者只需以给出的结点作为根结点来求解最小生成树即可。

求解最小生成树一般有两种算法，即 prim 算法与 kruskal 算法。这两个算法都是采用了贪心法的思想,只是贪心的策略不太一样。

prim 算法

prim 算法（读者可以将其读作“普里姆算法”）解决的是最小生成树问题，即在一个给定的无向图 G(V,E)中求一棵生成树 T，使得这棵树拥有图 G 中的所有顶点，且所有边都是来自图 G 中的边，并且满足整棵树的边权之和最小。

（邻接矩阵版）

n,m=map(int,input().split())#输入顶点数,边数
mg=[[float('inf')]*n for i in range(n)]
d=[float('inf')]*n#地点到达各点的最短路径长度
vis=[False]*n#标记数组
 
def prim():
    d[0]=0#标记起始点到集合S的距离为0
    ans=0#存放最小生成树的边权之和
    for i in range(n):
        u=-1
        MIN=float('inf')
        for j in range(n):
            if vis[j]==False and d[j]#找到未访问的顶点中d[]最小的
                u=j
                MIN=d[j]
        if u==-1:#找不到小于INF的d[u]，则剩下的顶点何集合S不连通
            return -1
        vis[u]=True
        ans+=d[u]
        for v in range(n):
            if vis[v]==False and mg[u][v]!=float('inf') and mg[u][v]
                d[v]=mg[u][v]
    return ans
for i in range(m):
    u,v,w = map(int, input().split())
    mg[u][v]=mg[v][u]=w
 
ans=prim()
print(ans)

和Dijkstra算法的代码进行比较后发现, Dijkstra算法和prim算法只有优化d[v]的部分不同，而其他语句都是相同的。这再次说明: Dijkstra 算法和 prim 算法实际上是相同的思路，只不过是数组 d[]的含义不同罢了。

kruskal 算法

kruskal 算法（读者可以将其读作“克鲁斯卡尔算法”）同样是解决最小生成树问题的一个算法。和 prim 算法不同，kruskal 算法采用了边贪心的策略，其思想极其简洁，理解难度比prim 算法要低很多。

kruskal 算法的基本思想为：在初始状态时隐去图中的所有边，这样图中每个顶点都自成一个连通块。之后执行下面的步骤：

①对所有边按边权从小到大进行排序。

② 按边权从小到大测试所有边，如果当前测试边所连接的两个顶点不在同一个连通块。中,则把这条测试边加入当前最小生成树中;否则,将边舍弃。

③ 执行步骤②，直到最小生成树中的边数等于总顶点数减 1 或是测试完所有边时结束。而当结束时如果最小生成树的边数小于总顶点数减1，说明该图不连通。

对 kruskal 算法来说，由于需要判断边的两个端点是否在不同的连通块中,因此边的两个端点的编号一定是需要的;而算法中又涉及边权,因此边权也必须要有。于是又有了下面两个问题。

① 如何判断测试边的两个端点是否在不同的连通块中。

② 如何将测试边加入最小生成树中。

事实上,对这两个问题,可以换一个角度来想。如果把每个连通块当作一个集合,那么就可以把问题转换为判断两个端点是否在同一个集合中，而这个问题在前面讨论过——对，就是并查集。并查集可以通过查询两个结点所在集合的根结点是否相同来判断它们是否在同一个集合,而合并功能恰好可以把上面提到的第二个细节解决,即只要把测试边的两个端点所在集合合并,就能达到将边加入最小生成树的效果。

另外,一定会有读者疑惑,使用kruskal算法能否保证最后一定能形成一棵连通的树?这个问题的前提是必须在连通图下讨论,如果图本身不连通,那么一定无法形成一棵完整的最小生成树。而对问题本身的讨论则需要分3个部分:

① 由于图本身连通，因此每个顶点都会有边连接。而一开始每个结点都视为一个连通块，因此在枚举过程中一定可以把每个顶点都访问到,且只要是第一次访问某个顶点,对应的边一定会被加入最小生成树中，故图中的所有顶点最后都会被加入最小生成树中。

② 由于只有当测试边连接的两个顶点在不同的连通块中时才将其加入最小生成树,因此一定不会产生环。而如果有两个连通块未被连接,要么它们本身就无法被连接（也就是非连通图),要么它们之间一定有边。由于所有边都会被测试,因此两个连通块最终一定会被连接在一起。故最后一定会生成一个连通的结构。

③ 由于算法要求当最小生成树中的边数等于总顶点数减1时结束,因此由连通、边数等于顶点数减1这两点可以确定,最后一定能生成一棵树。

最小生成树-Kruskal算法

def find(x):#并查集查询函数
    a=x
    while x!=father[x]:
        x=father[x]
    while(a!=father[a]):#路径压缩
        z=a
        a=father[a]
        father[z]=x
    return father[x]
 
def kruskal(n,edges):
    '''KRUSKAL算法实现'''
    ans=0#为所求边权之和
    Num_Edge=0#为当前生成树的边数
    #minu_tree = []#记录路径
    for i in range(n):
        father[i] = i#并查集初始化
    edges.sort()  # 所有边按边权从小到大排序
    for edge in edges:#枚举所有边
        w, u, v = edge
        if find(u) != find(v):#查询测试边两个端点所在集合的根结点，看是不是在一个集合中（根结点相等）
            father[find(u)]=find(v)#合并集合（即把测试边加入最小生成树中）
            #minu_tree.append(edge)#记录路径
            ans+=w#边权之和增加测试边的边权
            Num_Edge+=1#当前生成树的边数+1
            if Num_Edge==n-1:#边数等于顶点数减1时结束算法
                break
    if Num_Edge!=n-1:#无法连通时返回-1
        return -1
    else:
        return ans#返回最小生成树的边权之和
 
n,m=map(int,input().split())
edges = []
father =[0]*n
for i in range(m):
    u,v,w=map(int,input().split())
    edges.append((w,u,v))
 
print(kruskal(n,edges))
 

可以看到, kruskal算法的时间复杂度主要来源于对边进行排序,因此其时间复杂度是O(ElogE),其中E为图的边数。显然kruskal适合顶点数较多、边数较少的情况,这和prim算法恰好相反。于是可以根据题目所给的数据范围来选择合适的算法，即如果是稠密图（边多),则用prim算法;如果是稀疏图(边少),则用kruskal算法。

拓扑排序

有向无环图

如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图(Directed Acyclic Graph, DAG)。图给出了几个DAG的例子。

拓扑排序

拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图G中的任意两个顶点 u、v，如果存在边 u->v，那么在序列中 u 一定在 v 前面。这个序列又被称为拓扑序列。

关键路径