图论 python版

无负权图求最短路->dijkstra算法

朴素版

n, m = map(int, input().split())
mmap = [[] for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    mmap[a].append((b, c))

def dijkstra():
    dist = [0x3f3f3f3f for i in range(n + 1)]
    dist[1] = 0
    st = [False for i in range(n + 1)]
    #只需n - 1次，第n - 1次会算出dist[n]的值
    for i in range(n - 1):
        t = -1
        for j in range(1, n + 1):
            if not st[j] and (t == -1 or dist[j] < dist[t]):
                t = j
        for x in mmap[t]:
            if dist[x[0]] > dist[t] + x[1]:
                dist[x[0]] = dist[t] + x[1]
        st[t] = True
    if dist[n] == 0x3f3f3f3f:
        print(-1)
    else:
        print(dist[n])

dijkstra()

优先队列优化

n, m = map(int, input().split())
mmap = [[] for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    mmap[a].append((b, c))

import heapq
def dijkstra():
    dist = [0x3f3f3f3f for i in range(n + 1)]
    dist[1] = 0
    st = [False for i in range(n + 1)]
    queue = []
    heapq.heappush(queue, (0, 1))
    while queue:
        x = heapq.heappop(queue)
        if st[x[1]]:
            continue
        st[x[1]] = True
        for u in mmap[x[1]]:
            if dist[u[0]] > dist[x[1]] + u[1]:
                dist[u[0]] = min(dist[u[0]], dist[x[1]] + u[1])
                heapq.heappush(queue, (dist[u[0]], u[0]))
    if dist[n] == 0x3f3f3f3f:
        print(-1)
    else:
        print(dist[n])

dijkstra()

有负权图求最短路->spfa算法

求最短路

n, m = map(int, input().split())
mmap = [[] for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    mmap[a].append((b, c))

from collections import deque
def spfa():
    st = [False for i in range(n + 1)]
    st[1] = True
    dist = [0x3f3f3f3f for i in range(n + 1)]
    dist[1] = 0
    queue = deque()
    queue.append(1)
    while queue:
        x = queue.popleft()
        st[x] = False
        for u in mmap[x]:
            if dist[u[0]] > dist[x] + u[1]:
                dist[u[0]] = dist[x] + u[1]
                if not st[u[0]]:
                    queue.append(u[0])
                    st[u[0]] = True
    if dist[n] > 0x3f3f3f3f // 2:
        print('impossible')
    else:
        print(dist[n])
spfa()

求有无负环

n, m = map(int, input().split())
mmap = [[] for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    mmap[a].append((b, c))

from collections import deque
def spfa():
    st = [False for i in range(n + 1)]
    dist = [0x3f3f3f3f for i in range(n + 1)]
    cnts = [0 for i in range(n + 1)]
    queue = deque()
    #记得全部加入队列
    for i in range(1, n + 1):
        queue.append(i)
        st[i] = True
    while queue:
        x = queue.popleft()
        st[x] = False
        for u in mmap[x]:
            if dist[u[0]] > dist[x] + u[1]:
                dist[u[0]] = dist[x] + u[1]
                cnts[u[0]] = cnts[x] + 1
                if cnts[u[0]] >= n:
                    print('Yes')
                    return
                if not st[u[0]]:
                    queue.append(u[0])
                    st[u[0]] = True
    print('No')
spfa()

最小生成树

稠密图->Prim 与朴素版dijkstra极其相似

n, m = map(int, input().split())
mmap = [[] for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    mmap[a].append((b, c))
    mmap[b].append((a, c))

def prim():
    res = 0
    dist = [0x3f3f3f3f for i in range(n + 1)]
    dist[1] = 0
    st = [False for i in range(n + 1)]
    #执行n次，因为res需要加n次
    for i in range(n):
        t = -1
        for j in range(1, n + 1):
            if not st[j] and (t == -1 or dist[j] < dist[t]):
                t = j
        if dist[t] == 0x3f3f3f3f:
            print("impossible")
            return
        res += dist[t]
        for x in mmap[t]:
            if dist[x[0]] > x[1]:
                dist[x[0]] = x[1]
        st[t] = True
    print(res)

prim()

稀疏图->Kruskal

class Node:
    def __init__(self, a, b, w):
        self.a = a
        self.b = b
        self.w = w
n, m = map(int, input().split())
edges = []
p = [i for i in range(n + 1)]
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append(Node(a, b, w))
edges.sort(key = lambda x : x.w)

def find(x):
    if not x == p[x]:
        p[x] = find(p[x])
    return p[x]

res = 0
cnt = 0
for i in range(m):
    a = find(edges[i].a)
    b = find(edges[i].b)
    if not a == b:
        res += edges[i].w
        cnt += 1
        p[a] = b
if cnt < n - 1:
    print('impossible')
else:
    print(res)