单源最短路径问题的相关总结

单源最短路径问题的相关总结

什么是单源最短路，就是图中一个顶点到其他各个顶点的最短路径

在学习搜索中，有两种也是解决单源最短路径的，分别是bfs和01bfs

普通的深度优先搜索算法只能解决边权全部相同且非负的最短路；

01bfs只能解决边权要么为0，要么为1的情况。

常规版dijkstra算法

基于贪心思想，只能解决非负权图的单源最短路径

算法流程：

1）准备工作：

创建一个长度为n的dist数组，其中dist[i]表示的是从起点到i节点的最短路

创建一个长度为n的bool数组st，其中st[i]表示第i点是否已经确定了路径

2）初始化：

dist[1]=0，其余表示无穷大，表示还没有找到最短路

3）重复：

在所有没确定最短路的点中，找出最短路长度最小的点u。打上确定最短路的标记，然后对u的出边进行松弛操作，重复上述操作，直到所有的点的最短路都确定出来

#include <iostream>
#include<vector>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1e4_10,INF=2147483647;
int n,m,s;
vector<PII> edges[N];
LL dist[N];
bool st[N];
void dijkstra()
{
	for(int i=0;i<=n;i++) dist[i]=INF;
    dist[s]=0;
    for(int i=1;i<n;i++)
    {
        int u=0;
    for(int j=1;j<=n;j++)
    {
		if(!st[j]&&dist[j]<dist[u]) u=j;
    }
    st[u]=true;
    for(auto& t:edges[u])
    {
		int v=t.first,w=t.second;
        if(dist[u]+w<dist[v])
        {
			dist[v]=dist[u]+w;
        }
    }
}
    for(int i+1;i<=n;i++)
    {
		cout<<dist[i]<<" ";
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
		int u,v,w;
        cin>>u>>v>>w;
        edges[u].push_back({v,w});
    }
    dijkstra();
	return 0;
}

堆优化的dijkstra算法

与上面不同之处，也就是优化的地方在于，创建了一个小根堆用于维护更新后的节点

代码如下：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,m,s;
vector<PII> edges[N];
bool st[N];
int dist[N];
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,s});
    dist[s]=0;
    while(heap.size())
    {
		auto t=heap.top();heap.pop();
        int u=t.second;
        if(st[u]) continue;
        st[u]=true;
        for(auto&t:edges[u])
        {
			int v=t.first,w=t.second;
            if(dist[u]+w<dist[v])
            {
				dist[v]=dist[u]+w;
                heap.push({dist[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
		int x,y,z;
        cin>>x>>y>>z;
        edges[x].push_back({y,z});
    }
    dijkstra();
    return 0;
}

bellman_ford算法

基于松弛操作的算法，可以求出有负权图的最短路，并且可以对最短路不存在的情况进行判断

算法核心思想：不断尝试对图上每一条边进行松弛，直到所有的点无法松弛为止

最多重复多少轮松弛操作？

在最短路存在的情况下，由于一次松弛操作会使得最短路的边数至少增加1，而最短路的边数最多为n-1.因此最多执行松弛操作n-1轮。故时间复杂度为O（nm)

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int ,int> PII;
const int N=1e4+10,INF=2147483647;
int n,m,s;
vector<PII> edges[N];
int dist[N];
void bf()
{
    for(int i=0;i<n;i++) dist[i]=INF;
    dist[s]=0;
    bool flag=false;
    for(int u=1;u<=n;u++)
    {
        if(dist[u]==INF) continue;
        for(auto &t:edge[u])
        {
			int v=t.first,w=t.second;
            if(dist[u]+w<dist[v])
            {
                dist[v]=dist[u]+w;
                flag=true;
            }
        }
    }
    if(flag==false) break;
    
}
for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
		int u,v,w;
        cin>>u>>v>>w;
        edges[u].push_back({v,w});
    }
    bf();
return 0;
}

spfa算法

用队列进行优化BF算法 维护”哪些结点可能会引起松弛操作“

注意没有负权边最好使用Dijkstra算法

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int ,int> PII;
const int N=1e4+10,INF=2147483647;
int n,m,s;
vector<PII> edges[N];
int dist[N];
bool st[N];
void spfa()
{
	for(int i=0;i<=n;i++) dist[i]=INF;
    queue<int> q;
    q.push(s);
    dist[s]=0;
    st[s]=true;
    while(q.size())
    {
        auto a=q.front();q.pop();
        st[a]=false;
        for(auto &t:edges[a])
        {
            int b=t.first,c=t.second;
            if(dist[a]+c<dist[b])
            {
				dist[b]=dist[a]+c;
                if(!st[b])
                {
				q.push(b);
                    st[b]=true;
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
	int a,b,c;
        cin>>a>>b>>c;
        edges[a].push_back({b,c});
    }
	spfa();
}