随意发一个帖子

沈思邈

2025-09-27 15:18:56

发布于：上海

44阅读

0回复

0点赞

这个帖子是图论算法的合集，你会看到：
· 图的存储
· 图的遍历
· 并查集
· 最小生成树
· 最短路
· 拓扑排序

图的存储

图的存储分为两种：邻接表和邻接矩阵

邻接矩阵存图：

邻接矩阵存图思想很简单：
对于无权图，如果 $i$ 和 $j$ 有一条边相连，那么 $graph[i][j]=1$ ，否则 $graph[i][j]=0$
对于有权图，如果 $i$ 和 $j$ 有一条权值为 $k$ 的边相连，则 $graph[i][j]=k$ ，否则 $graph[i][j]=\infty$
C++模板代码：

const int N=5050,INF=0x3f3f3f3f;
int graph[N][N];
void Directed_Weighted_Graph(){
    memset(graph,INF,sizeof(graph));
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u][v]=w;
    }
}
void Directed_Unweighted_Graph(){
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u][v]=1;
    }
}
void Undirected_Weighted_Graph(){
    memset(graph,INF,sizeof(graph));
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u][v]=w;
        graph[v][u]=w;
    }
}
void Undirected_Unweighted_Graph(){
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u][v]=1;
        graph[v][u]=1;
    }
}

Python模板代码：

def Directed_Weighted_Graph():
    graph = [[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u][v]=w
def Directed_Unweighted_Graph():
    graph = [[0 for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u][v]=1
def Undirected_Weighted_Graph():
    graph = [[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u][v]=w
        graph[v][u]=w
def Undirected_Unweighted_Graph():
    graph = [[0 for i in range(n+1)] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u][v]=1
        graph[v][u]=1

空间复杂度： $O(V^2)$
练习：
A358. 有向无权图1
A355. 有向带权图1
A352. 无向无权图1

邻接表存图：

我们会发现，邻接矩阵存图，对于稀疏图而言，浪费了太多空间在 $0$ 或 $\infty$ 上，这会导致当 $n$ 越来越大，但是图是稀疏图的时候，会开不下邻接矩阵。因此，我们可以把邻接矩阵中所有的 $0$ 或者 $\infty$ 去掉，变成邻接表， $adj[i]$ 变成一个（C++）向量或者（Python）列表动态添加边的信息。
C++模板：

#define pir pair<int,int>
#define x first
#define y second
#define pb push_back
const int N=2e5+10;
void Directed_Weighted_Graph(){
    vector<pir>graph[N];
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u].pb({v,w});
    }
}
void Directed_Unweighted_Graph(){
    vector<int>graph[N];
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u].pb(v);
    }
}
void Undirected_Weighted_Graph(){
    vector<pir>graph[N];
    int u,v,w;
    while(m--){
        cin>>u>>v>>w;
        graph[u].pb({v,w});
        graph[v].pb({u,w});
    }
}
void Undirected_Unweighted_Graph(){
    vector<int>graph[N];
    int u,v;
    while(m--){
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
}

Python模板代码：

def Directed_Weighted_Graph():
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u].append((v,w))
def Directed_Unweighted_Graph():
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u].append(v)
def Undirected_Weighted_Graph():
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v,w=map(int,input.split())
        graph[u].append((v,w))
        graph[v].append((u,w))
def Undirected_Unweighted_Graph():
    graph = [[] for i in range(n+1)]
    while m>0:
        m-=1
        u,v=map(int,input.split())
        graph[u].append(v)
        graph[v].append(u)

空间复杂度： $O(E)$
练习：
A351. 有向带权图2
A650. 有向无权图2

图的遍历

图的遍历，主要分为深度优先遍历和广度优先遍历，内容和深度优先搜索（ $Depth-First-Search$ ）与广度优先搜索（ $Breadth-First-Search$ ）几乎一样。

深度优先遍历：

以邻接表为例，深度优先遍历就是不走回头路，一直往下遍历，遍历到没有未访问的结点就返回。
C++模板代码：

const int N=2e5+10;
vector<int>graph[N]; //邻接表
bool vis[N]; //vis数组标记
void dfs(int u){
    cout<<u<<" "; //输出
    vis[u]=1; //标记
    for(auto&v:graph[u]) //遍历所有能够到达的点
        if(!vis[v]) //没有标记过则访问，避免重复遍历
            dfs(v); //递归遍历
    return;
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
vis=[0 for i in range(n+1)] #列表生成式初始化标记数组
def dfs(u):
    print(u,end=" ") #输出
    vis[u]=1 #标记
    for v in graph[u]: #遍历所有能到达的点
        if not vis[v]: #没有标记过则访问，避免重复遍历
            dfs(v) #递归遍历
    return

广度优先遍历：

依然以邻接表为例，广搜像水流一样要流经所有结点，虽然搜索时比深搜效率快很多，但是在这里和深搜遍历就效率上来谈没什么大的区别。
C++模板代码：

const int N=2e5+10;
vector<int>graph[N]; //邻接表
bool vis[N]; //vis数组标记
void bfs(int u){
    queue<int>q; //广搜必备队列
    vis[u]=1; //标记
    q.push(u); //加入队列
    while(q.size()){ //循环直到队列中没有元素
        u=q.front(); //取出队首
        q.pop(); //弹出队首
        cout<<u<<" "; //输出
        for(auto&v:graph[u]){ //遍历所有能够到达的点
            if(!vis[v]){ //没有标记过则访问，避免重复遍历
                vis[v]=1; //标记
                q.push(v); //加入队列
            }
        }
    }
    return;
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
vis=[0 for i in range(n+1)] #列表生成式初始化标记数组
def bfs(u):
    queue=[u] #创造队列
    vis[u]=1 #标记
    while len(queue): #循环直到队列中没有元素
        u=queue.pop(0) #取出并弹出队列
        print(u,end=" ") #输出
        for v in graph[u]: #遍历所有能够到达的点
            if not vis[v]: #没有标记过则访问，避免重复遍历
                vis[v]=1 #标记
                q.append(v) #加入队列
    return

时间复杂度：都是 $O(V)$
练习：
A4762. 关系网络

并查集：

并查集（ $Union-Find$ ）是一种用于管理‌不相交集合‌的高效数据结构，主要解决元素的‌分组、合并与连通性查询‌问题。主要分成查询（ $Find$ ）和合并（ $Unite$ ）两个操作。可以形象地想象成是认“义父”操作
C++模板代码：

const int N=5050;
int pa[N];
//核心代码
int find(int x){ //查找函数
    if(pa[x]==x)return x; //找到根源，即自己的祖先就是自己
    return pa[x]=find(pa[x]); //递归去寻找，将结果赋值给pa[x]进行路径压缩，防止超时
}
void unite(int a,int b){ //合并函数
    int ra=find(a),rb=find(b); //找到各自的祖先，判断是否为同一个祖先
    if(ra!=rb)pa[rb]=ra; //进行合并操作
}
//初始化
for(int i=1;i<=n;i++)
    pa[i]=i; //默认祖先是自己

Python模板代码：

pa=[i for i in range(n+1)] #列表生成式自带初始化
#核心代码
def find(x): #查找递归
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
def unite(a=int,b=int): #合并
    ra,rb=find(a),find(b) #利用元组特性进行赋值
    if ra!=rb: #祖先不同，进行合并
        pa[rb]=ra #朴素的合并操作

单次查找函数的时间复杂度： $O(\log E)$
总时间复杂度： $O(E\log E)$
练习：
A567. 亲戚1
A565. 亲戚2

生成树：

在连通图 $G$ 中，对于 $\forall u、v\in G.V$ ，有且仅有一条路，且生成树中不存在回路。

最小生成树：

是所有的生成树中边权值和最小的一棵生成树。常见算法有 $Kruskal$ （克鲁斯卡尔）和 $Prim$ （普里姆）

求最小生成树的方法：

· Kruskal 算法：

1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 $u、v$ 两个结点的边
3、通过并查集判断 $u、v$ 两个结点是否联通，如果不联通则合并两个结点
4、选到 $n-1$ 条边的时候，根据树的定义可以直接返回
C++模板代码：

struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
}e;
bool cmp(Edge a,Edge b){ //比较函数，因为权值和最小，所以按照边权值从小到大排序
    return a.w<b.w;
}
vector<Edge>edges; //存连通图的每条边
int n,m,c[N],ans,cnt;
int find(int x){ //并查集 查询函数
    if(c[x]==x)return x;
    return c[x]=find(c[x]); //路径压缩
}
void Kruskal(){
    for(int i=1;i<=n;i++)c[i]=i; //并查集初始化
    sort(edges.begin(),edges.end(),cmp); //按边的权值从小到大的顺序将边进行排序
    for(auto edge:edges){ //按顺序遍历数组
        int cu=find(edge.u),cv=find(edge.v); //找到两个结点所在的联通子图
        if(cu!=cv){ //两点并未联通
            c[cv]=cu; //合并两个结点，即并查集
            cnt++; //计数，可以在下面节约时间
            ans+=edge.w; //加上权值
        }
        if(cnt==n-1)return; //已经找到一棵最小生成树，退出循环
    }
}

Python模板代码：

edges=[] #存边，而非邻接表
pa=[i for i in range(n+1)] #列表生成式，并查集初始化
def find(x): #并查集的查找函数
    if pa[x]==x: #找到根源，自己的祖先是自己
        return x #返回结果
    pa[x]=find(pa[x]) #路径压缩
    return pa[x] #返回结果
def Kruskal():
    edges.sort(key=lambda x:x[2]) #按照边权从小到大排序进行贪心
    cnt=ans=0 #cnt计数，ans最小边权和
    for u,v,w in edges: #遍历
        cu,cv=find(u),find(v) #找到祖先
        if cu!=cv: #两个点未连通，进行边权添加，连入同一棵最小生成树
            cnt+=1 #选的边数+1
            ans+=w #更新答案
            pa[cv]=cu; #合并
        if cnt==n-1: #n个顶点n-1条边，选到了提前退出
            break

时间复杂度： $O(E\log E)$
空间复杂度： $O(V+E)$

· Prim算法：

1、初始化距离数组为 $\infty$ ，选择初始结点，将其距离设为 $0$
2、遍历所有结点中未标记的结点，选择其中距离最小的结点，进行标记
3、从该结点出发，遍历其能够到达的所有结点，更新其距离
4、重复执行操作 $2$ 和 $3$ 直到全部顶点都被标记
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,u,v,w,ans,dist[N];
bool vis[N];
struct Node{
    int v,w; //v表示目标结点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void prim(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    for(int i=1;i<=n;i++){ //重复执行n次，包括传入的参数u
        u=0; //和赋值为0的u比较
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的结点
                u=j; //更新u
        vis[u]=1; //标记为已到达
        for(auto node:graph[u]){ //遍历其相邻结点
            int v=node.v,w=node.w;
            if(!vis[v]) //一定要未被标记过，否则会重复
                dist[v]=min(dist[v],w); //更新，因为结果是累加的，所以这边更新后只要保留w
        }
    }
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def prim(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号结点比较，且0号结点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的结点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前结点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],w) #更新，结果是累加的，所以只保留w

时间复杂度： $O(V^2)$
空间复杂度： $O(V+E)$
练习：
A555. 最小生成树

最短路算法：

即求从结点 $u$ 到结点 $v$ 所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点 $u$ 到所有其它结点 $v$ 的算法，而多源最短路算法可以求 $\forall u \in G.V$ 作为起点到其它结点 $v$ 的最短路。

单源最短路算法：

常见的有 $Dijkstra$ （迪杰斯特拉）、 $Bellman-Ford$ （贝尔曼-福特）和 $SPFA$ 三个算法。

求单源最短路的方法：

· Dijkstra

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
    int v,w; //v表示目标结点，w表示边权值
};
vector<Node>graph[N]; //邻接表存图
void dijkstra(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，类似冒泡排序，可以省最后一次
        u=0; //和赋值为0的无效u比较
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u]) //通过比较找到距离最近的结点
                u=j; //更新u
        vis[u]=1; //标记为已到达
        for(auto node:graph[u]){ //遍历其相邻结点
            int v=node.v,w=node.w;
            if(!vis[v]) //一定要未被标记过，否则会重复
                dist[v]=min(dist[v],dist[u]+w); //更新
                //和Prim不同的是这里是和dist[u]+w比较更新
        }
    }
}

Python模板代码：

graph=[[] for i in range(n+1)] #列表生成式创建邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
vis=[0 for i in range(n+1)] #列表生成式初始化
def dijkstra(u): #核心函数
    dist[u]=0 #u到u距离为0
    for i in range(n): #循环n次找开始更新的点，包括u
        u=0 #和赋值为极大值的0号结点比较，且0号结点不参与更新
        for j in range(1,n+1): #遍历
            if not vis[j] and dist[j]<dist[u]: #通过比较找到距离最近的结点
                u=j #更新u
        vis[u]=1 #标记为已到达
        for v,w in graph[u]: #遍历从当前结点出发的每一条边
            if not vis[v]: #未标记过以防重复
                dist[v]=min(dist[v],dist[u]+w) #更新，注意最短路里面就需要累加

时间复杂度： $O(V^2)$
空间复杂度： $O(V+E)$

· Dijkstra 的优化

根据上面代码，用 $O(V^2)$ 的时间复杂度取求最短路无疑是有点浪费时间的，时间都花在了找最小值上面。考虑利用 $STL$ 容器的特性来优化 $Dijkstra$ ，我们需要一个能够动态找最小值的容器。
因此，我们可以利用优先队列（堆）动态找到最小值来优化 $Dijkstra$ 算法：
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
bool vis[N];
struct Node{
    int v,w;
    friend bool operator<(const Node&a,const Node&b){
    	return a.w>b.w; //重载运算符
	}
};
vector<Node>graph[N];
void dijkstra(int u){
	priority_queue<Node>q; //优先队列取最小值
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    q.push({u,0}); //初始结点加入队列
    while(q.size()){ //bfs思路
    	Node f=q.top(); //取出队首
    	q.pop(); //弹出队首
    	u=f.v;
    	if(vis[u])continue; //已被标记不再入队
        vis[u]=1; //标记为已到达
    	for(auto i:graph[u]){ //遍历其相邻结点
    		if(dist[i.v]>dist[u]+i.w){
    			dist[i.v]=dist[u]+i.w; //更新
    			q.push({i.v,dist[i.v]}); //入队
			}
		}
	}
}

Python模板代码：

graph=[[] for i in range(n+1)]
dist=[0x3f3f3f3f for i in range(n+1)]
vis=[0 for i in range(n+1)]
class Priority_Queue(): #手搓堆（优先队列），你也可以用heapq库
    def __init__(self):
#堆就是完全二叉树，利用完全二叉树的性质，父节点编号为i，子节点编号为2i和2i+1，用列表建堆
        self.heap=[(0,0)] #堆的主要结构，强制变成1-based
        self.size=0 #记录堆的大小
    def push(self,val): #插入
        self.size+=1
        self.heap.append(val) #插入到末尾
        son=self.size
        while son>1: #向上比较
            pa=son//2
            if self.heap[pa][1]<=self.heap[son][1]: #无法继续向上爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            son=pa
    def pop(self): #移除
        self.heap[1]=self.heap[self.size] #变成堆顶
        self.heap.pop(self.size) #弹出末尾
        self.size-=1
        pa=1
        while pa*2<=self.size: #向下比较
            son=pa*2
            if son<self.size and self.heap[son+1][1]<=self.heap[son][1]:
                son+=1 #更新成更小的子节点
            if self.heap[pa][1]<=self.heap[son][1]: #无法向下爬则退出
                break
            self.heap[pa],self.heap[son]=self.heap[son],self.heap[pa] #交换
            pa=son
    def top(self): #取堆顶元素
        return self.heap[1]
def dijkstra(u):
    pq=Priority_Queue() #小根堆动态取最小值
    dist[u]=0 #u到u距离为0
    pq.push((u,0)) #加入队列
    while pq.size: #bfs思路
        f=pq.top() #取出队首
        pq.pop() #弹出队首
        u=f[0]
        if vis[u]: #已被标记不再入队
            continue
        vis[u]=1 #标记
        for v,w in graph[u]: #遍历可到达结点
            if dist[v]>dist[u]+w: #可以松弛
                dist[v]=dist[u]+w #松弛更新
                pq.push((v,dist[v])) #加入队列

时间复杂度： $O(V\log V+E\log V)$

Dijkstra 不适用的情况：

根据 $Dijkstra$ 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。

· Bellman-Ford：

1、遍历所有的边
2、从边的起点到终点做松弛操作
优化：如果没有进行过松弛操作则退出循环
C++模板代码：

const int MAXN=0x3f3f3f3f;
const int N=5050;
int n,m,k,u,v,w,dist[N];
struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
    for(int i=0;i<=n;i++)dist[i]=MAXN; //初始化
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，和Dijkstra一样
        bool opt=0; //用于判断是否进行松弛操作
        for(auto edge:graph){ //按顺序遍历数组
            int u=edge.u,v=edge.v,w=edge.w;
            if(dist[u]+w<dist[v]) //注意这里是有向图，无向图还需交换u和v
                dist[v]=dist[u]+w,opt=1; //松弛操作后可以进行标记
        }
        if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
    }
}

Python模板代码：

edges=[] #存边，而非邻接表
dist=[0x3f3f3f3f for i in range(n+1)] #列表生成式初始化
def Bellman_Ford(u):
    dist[u]=0 #u到u距离为0
    for i in range(n): #一共枚举n次
        opt=0 #用于判断是否进行松弛操作
        for u,v,w in edges: #枚举所有边
            if dist[u]+w<dist[v]: #可以进行松弛
                dist[v]=dist[u]+w #松弛
                opt=1 #标记
        if not opt: #没有进行松弛，那么下一轮也不会松弛，退出循环
            break

· Bellman_Ford 变形——不超过 $k$ 条边的最短路

对于某些题目，要求走的边数不超过 $k$ 且求最短路，普通的 $Bellman-Ford$ 算法肯定行不通。此时，我们可以使用 $dp$ 思想，来进行最短路的计算，如下：
C++模板代码：

#define pb push_back
#define int long long
const int MAXN=0x3f3f3f3f; //防止做加法超出int范围 
const int N=5050;
int n,m,k,u,v,w,dist[N][N]; //dist[i][j]表示选用i条边到达j的最短路，必然不会超过n-1条边
struct Edge{
    int u,v,w; //u、v表示两个端点，w表示边权值
};
vector<Edge>graph; //存图的每条边
void Bellman_Ford(int u){
    memset(dist,MAXN,sizeof(dist)); //初始化
    dist[0][u]=0; //以u为初始结点，距离为u到u的距离，即0
    for(int i=1;i<n;i++){ //重复n-1次，和Dijkstra一样
        bool opt=0; //用于判断是否进行松弛操作
        for(auto edge:graph){ //按顺序遍历数组
            int u=edge.u,v=edge.v,w=edge.w;
            if(dist[i-1][u]+w<dist[i][v]) //注意这里是有向图，无向图还需交换u和v
                dist[i][v]=dist[i-1][u]+w,opt=1; //松弛操作后可以进行标记
        }
        if(!opt)return; //如果这次没有操作，下次也不会有操作，退出节省时间
    }
}

Python模板代码：

edges=[] #存边
dist=[[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)] #dist[i][j]选i条边到j最短路
def Bellman_Ford(u):
    dist[0][u]=0 #u到u的距离为0
    for i in range(1,n): #重复n-1次
        opt=0 #是否进行松弛
        for u,v,w in edges: #按顺序便利数组
            if dist[i-1][u]+w<dist[i][v]: #可以进行松弛
                dist[i][v]=dist[i-1][u]+w #松弛，因为边数不超过k所以不可以降维
                opt=1 #标记
            if not opt:
                return #小优化

时间复杂度： $O(VE)$
空间复杂度： $O(V+E)$

· SPFA：

$SPFA$ （ $Shortest\,\,Path\,\,Faster\,\,Algorithm$ ）是 $Bellman-Ford$ 算法的进阶版本，通过队列来对其进行优化。
C++模板代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int N=5050;
const int MAXN=0x3f3f3f3f;
int n,m,k,u,v,w,dist[N],cnt[N];
bool vis[N];
struct node{
    int v,w; //v表示目标结点，w表示边权值
};
vector<node>graph[N]; //邻接表存图
void spfa(int u){
    for(int i=1;i<=n;i++)dist[i]=MAXN,vis[i]=0; //初始化
    queue<int>q;
    dist[u]=0; //以u为初始结点，距离为u到u的距离，即0
    q.push(u);
    while(q.size()){
        u=q.front(); //取出队首，同bfs
        q.pop(); //弹出队首，同bfs
        vis[u]=0; //撤销标记，因为spfa可以重复入队
        cnt[u]++; //计数
        if(cnt[u]>n)return; //和Bellman-Ford一样最多只能入队n次，大于n直接返回
        for(auto edge:graph[u]){ //按顺序遍历数组
            int v=edge.v,w=edge.w;
            if(dist[v]>dist[u]+w){ //判断是否可以进行松弛操作
                dist[v]=dist[u]+w; //松弛
                if(!vis[v]){ //如果未被标记说明不在队伍中，标记入队
                    vis[v]=1; //标记
                    q.push(v); //入队
                }
            }
        }
    }
}
signed main(){
    cin>>n>>m>>k;
    while(m--){
        cin>>u>>v>>w;
        graph[u].pb({v,w}); //注意这里是有向图
        //无向图再存一遍：graph[v].pb({u,w});
    }
    spfa(k);
    for(int i=1;i<=n;i++)cout<<(dist[i]!=MAXN?dist[i]:-1)<<" ";
    return 0;
}

时间复杂度： $O(kV)$ （ $k$ 为常数，通常是在 $[2,3]$ 之间）
空间复杂度： $O(V+E)$
队列空间复杂度： $0< x\leq O(V)$
练习：
A569. 单源最短路1

多源最短路算法：

一般用 $Floyd-Warshall$ 算法（也有版本叫它 $Floyed-Warshall$ ）。

求多源最短路的方法：

· Floyd-Warshall：

$Floyd-Warshall$ 算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
C++模板代码：

const int INF=0x3f3f3f3f; //极大值
int n,m,q,dp[110][110],u,v,w;
void Floyd_Warshall(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=i==j?0:INF; //初始化
    for(int k=1;k<=n;k++) //枚举所有的结点作为中转点
        for(int i=1;i<=n;i++) //枚举所有的结点作为起点
            for(int j=1;j<=n;j++) //枚举所有的结点作为终点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);//动态规划计算最短路
}

Python模板代码：

dp=[[0x3f3f3f3f for i in range(n+1)] for i in range(n+1)] #邻接矩阵初始化
for i in range(1,n+1):
    dp[i][i]=0 #u到u距离为0
def Floyd_Warshall():
    for k in range(1,n+1): #枚举所有的结点作为中转点
        for i in range(1,n+1): #枚举所有的结点作为起点
            for j in range(1,n+1): #枚举所有的结点作为终点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) #动态规划计算最短路

时间复杂度： $O(V^3)$
空间复杂度： $O(V^2)$

拓扑排序

图的拓扑排序定义：
对于有向无环图（简称 $DAG$ ）是将 $G$ 中所有顶点排成一个线性序列，使得 $\forall u,v\in G.V$ ，若边 $<u,v$ $>$ $\in G.E$ ，则 $u$ 在线性序列中出现在 $v$ 之前。
1、选择一个入度为0的顶点并输出
2、从网中删除此顶点及所有出边
3、重复操作 $1$ 和 $2$ 直到没有符合要求的点