单源最短路

单源最短路模板题

方法一：SPFA

python版本

推销一下下面的个人发明建边函数def Lin(a,b,c)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

#SPFA算法
def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = min(link[a][b],c)

def SPFA(start):
    queue = [start]
    inq = [False]*(n+1)  #判断是否在队列中
    dis = [float('inf')]*(n+1)
    dis[start] = 0
    inq[start] = True     #这是优化点，避免重复入队
    while queue:

        sam = queue.pop(0)
        inq[sam] = False

        for node in link[sam]:
            if dis[node] > dis[sam] + link[sam][node]:
                dis[node] = dis[sam] + link[sam][node]
                if inq[node] == True:  #如果在队列中则不管他
                    continue
                inq[node] = True
                queue.append(node)

    return dis


n,m,s,t = map(int,input().split())

link = {}
for i in range(m):
    a,b,c = map(int,input().split())
    Lin(a,b,c)
    Lin(b,a,c)


dis = SPFA(s)
#print(parent)
print(dis[t])

方法二： dijkstra优先队列优化

python版本

推销一下下面的个人发明建边函数def Lin(a,b,c)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

import heapq
def dijkstra(start):
    queue = []
    heapq.heappush(queue,(0,start))
    dis = [float('inf')]*(n + 1)
    vis = [False]*(n + 1)
    dis[start] = 0

    while queue:
        sam = heapq.heappop(queue)
        curDis = sam[0]
        curNode = sam[1]
        vis[curNode] = True
        if curNode not in link.keys():
            continue
        for node in link[curNode].keys():
            if vis[node] == False:
                if curDis + link[curNode][node] < dis[node]:
                    dis[node] = curDis + link[curNode][node]
                    heapq.heappush(queue,(dis[node],node))
    return dis

def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = min(link[a][b],c)

n,m,s,e = map(int,input().split())
link = {}
for i in range(m):
    a,b,c = map(int,input().split())
    Lin(a,b,c)
    Lin(b,a,c)

dis = dijkstra(s)
print(dis[e])

优先队列dijkstra

cpp版本

#include <iostream>
#include <algorithm>
#include <cstring>
#include<queue>
#include <vector>


using namespace std;

const int N = 5010,M = 6210 * 2;

int n,m,s,t;
int h[N],e[M],w[M],ne[M],idx;
int dis[N],queue[N];
bool vis[N];

typedef pair<int,int> PII;


void add(int a,int b,int c){
    e[idx] = b,w[idx] = min(w[idx],c),ne[idx] = h[a],h[a] = idx ++;
}
void dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,s});
    while (!heap.empty()){
        PII sam = heap.top();
        heap.pop();
        int curNode = sam.second, curDis = sam.first;
        vis[curNode] = true;
        for(int i = h[curNode];~i;i = ne[i]){
            int node = e[i];
            if (vis[node]) continue;
            if (curDis + w[i] < dis[node]){
                dis[node] = curDis + w[i];
                heap.push({dis[node],node});
            }
        }
    }
}




int main(){
    memset(h,-1,sizeof h);
    memset(w,0x3f,sizeof w);

    scanf("%d %d %d %d",&n,&m,&s,&t);

    while (m --){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    printf("%d\n",dis[t]);

    return 0;
}

SPFA

cpp版本

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>


using namespace std;

const int N = 5010,M = 6210 * 2;

int n,m,s,t;
int h[N],e[M],w[M],ne[M],idx;
int dis[N];
bool vis[N];

void add(int a,int b,int c){
    e[idx] = b,w[idx] = min(w[idx],c),ne[idx] = h[a],h[a] = idx ++;
}
void spfa(){
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    queue<int > queue;
    queue.push(s);
    vis[s] = true;
    while (queue.size()){
        int curNode = queue.front();
        queue.pop();
        vis[curNode] = false;
        for(int i = h[curNode] ; ~i ; i = ne[i]){
            int node = e[i];
            if(dis[node] > dis[curNode] + w[i]) {
                dis[node] = dis[curNode] + w[i];
                if (vis[curNode] == false) {
                    queue.push(node);
                    vis[node] = true;
                }
            }
        }
    }
}


int main(){
    memset(h,-1,sizeof h);
    memset(w,0x3f,sizeof w);

    scanf("%d %d %d %d",&n,&m,&s,&t);

    while (m --){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    spfa();
    printf("%d\n",dis[t]);

    return 0;
}