图论模板总结

2020-07-09 本文已影响0人 madao756

前言：图论那几个算法真的比较容易忘记，今天就来复习一下吧

0X00 模板总结

Dijkstra

算法本身就是用来求最短路径的

不能求带有负权边的情况，原因是：已经访问过的点可能被之后的负权更新导致 dist 变小。

def dij(s, e):
    dist[s] = 0
    for i in range(1,n+1):
        t = -1
        for j in range(1, n+1):
            if not st[j] and (t == -1 or dist[t] > dist[j]):
                t = j
        if t == -1: break
        st[t] = True
        for j in range(1, n+1):
            dist[j] = min(dist[j], g[t][j] + dist[t])
    return dist[e]

850. Dijkstra求最短路 II $O((V+E)logV)$

from heapq import heappush, heappop
def dij(s, e):
    dist = [float("inf")] * (1+n)
    st = [False] * (1+n)
    dist[s] = 0
    minHeap = [(0, s)]
    
    while minHeap:
        d, v = heappop(minHeap)
        if st[v]: continue
        if v not in graph: continue
        st[v] = True
        for v1 in graph[v]:
            if dist[v1] > d + graph[v][v1]:
                dist[v1] = d + graph[v][v1]
                heappush(minHeap, (d + graph[v][v1], v1))
    return -1 if dist[e] == float("inf") else dist[e]

SPFA

851. spfa求最短路

求最短路，可以有负权边，时间复杂度为 $O(VE)$

还有其他的用途放在其他博客专门总结。

from collections import deque
def spfa(s, e):
    dist = [float("inf")] * (1+n)
    dist[s] = 0
    st = [False] * (1+n)
    st[s] = True
    q = deque([s])
    
    while q:
        v = q.popleft()
        st[v] = False
        for v1, d in g[v]:
            if dist[v1] > dist[v] + d:
                dist[v1] = dist[v] + d
                if not st[v1]:
                    st[v1] = True
                    q.append(v1)
    
    return dist[e]

bellman-ford

853. 有边数限制的最短路这个算法就这一个作用：有边数限制的时候求最短路 时间复杂度是： $O()$

def bellFord(s, e, limit):
    dist[s] = 0
    
    for _ in range(limit):
        for i in range(1, n+1): backup[i] = dist[i]
        
        for i in range(m):
            a, b, c = edges[i]
            if dist[b] > backup[a] + c:
                dist[b] = backup[a] + c
        
    
    return dist[e]

Floyd

这个算法有很多其他用途，我会在其他博客中总结

854. Floyd求最短路 $O(n^3)$

def floyd():
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])