图论入门详解（拓扑排序，Dijkstra算法，SPFA算法）

目录

例题：公交线路

Dijkstra算法

适用范围：

主要思想：

实现细节：

代码实现：

 SPFA算法

适用范围：

主要思想：

代码实现：

拓扑排序模板

例题：公交线路

https://ac.nowcoder.com/acm/contest/26077/1007

题目描述

P市有n个公交站，之间连接着m条道路。P市计划新开设一条公交线路，该线路从城市的东站（s点）修建到西站（t点），请为P市设计一条满足上述条件并且最短的公交线路图。

输入描述:

第一行有4个正整数n，m，s，t。接下来m行，每行3个数a,b,v描述一条无向道路a——b，长度为v。

输出描述:

如果有解，输出一行，表示满足条件的最短公交线路的长度c。否则，输出“-1”

输入

3 3 1 2
1 2 3
2 3 4
1 3 5

输出

3

输入

3 3 1 2
1 2 5
2 3 3
1 3 1

输出

4

输入

3 1 1 1
1 2 1

输出

0

备注:

对于100%的测试数据：
1 ≤ s,t ≤ n ≤ 1000
1 ≤ m ≤ 10000
1 ≤ 道路的长度 ≤ 10000

最短路裸题，练手Dijkstra算法和SPFA算法

Dijkstra算法

适用范围：

最短路算法，求一个点到任意点的最短路径，适用于没有负权边的情况

本质是SPFA+贪心优化

主要思想：

从起点开始，每次找出离起点最近的点，这个点目前的最短路径必然是最短路径，因为其他点离起点更远，从其他点绕回这个点不可能必当前最短还短

实现细节：

用dis记录每个点到起点的最短路径，用vis记录该点到起点的最短路径是否已经被求出来了

用优先队列储存被更新过的点，没求出最短路的点中离起点最近的点必定不会有更短的路径，这个点就位于优先队列队首，每次取出然后更新与它相邻的点还没求出最短路的点即可

代码实现：

#include
using namespace std;int head[1005];     //存第一个点
int n,m,s,t;        //点数、边数、起点、终点struct ty{int t;          //存连接的点int l;          //存边长int next;       //存指针
}edge[20010];       //存边，无向边开2倍空间
int cnt=0;      //边数void addedge(int x,int y,int z){    //添加边edge[++cnt].l=z;    //边长edge[cnt].t=y;      //点编号edge[cnt].next=head[x];     //链式前向星head[x]=cnt;
}struct ty2{int dis;        //起点到该点最短距离int num;        //编号bool operator <(const ty2&a)const{  //重载运算符，放优先队列return dis>a.dis;           //默认大顶堆，反向定义}
};bool vis[1005];     //标记是否求出最短路径
int dis[1005];      //从起点到该点距离priority_queueq;   //优先队列，储存离起点最近的点
int Dij(){memset(dis,0x3f3f3f3f,sizeof(dis));dis[s]=0;           //初始化q.push({0,s});      //把起点放进去·/*ty2 tmp;            tmp.dis=0;tmp.num=s;q.push(tmp);  */while(!q.empty()){ty2 tmp2=q.top();       //一个一个点取出来q.pop();if(vis[tmp2.num])continue;  //如果已经找到最短路，返回vis[tmp2.num]=1;          //标记这个点最短路已经找见for(int i=head[tmp2.num];i!=-1;i=edge[i].next){     //枚举和这个点相连的所有点int y=edge[i].t;if(vis[y])continue;     //如果已经找到最短路，不用更新，直接返回if(dis[tmp2.num]+edge[i].l=0x3f3f3f3f)return -1;        //没找到返回-1return dis[t];      //找到了返回到终点的最短路径
}
int main(){cin>>n>>m>>s>>t;memset(head,-1,sizeof(head));       //初始化head为-1，要放在addedge之前while(m--){int x,y,z;cin>>x>>y>>z;       //读入addedge(x,y,z);     //无向边，存两次addedge(y,x,z);}cout<

#include
using namespace std;int head[1005];     //存第一个点
int n,m,s,t;        //点数、边数、起点、终点struct ty{int t;          //存连接的点int l;          //存边长int next;       //存指针
}edge[20010];       //存边
int cnt=0;      //边数void addedge(int x,int y,int z){    //添加边edge[++cnt].l=z;    //边长edge[cnt].t=y;      //点编号edge[cnt].next=head[x];     //链式前向星head[x]=cnt;
}queueq;        //队列储存被更新过的点int dis[1005];      //从起点到该点距离
bool vis[1005];     //标记是否在队列中int spfa(){memset(dis,0x3f3f3f3f,sizeof(dis));     //初始化dis[s]=0;vis[s]=1;q.push(s);      //起点入队while(!q.empty()){int x=q.front();        //每次取出队列一个点，更新和他相邻的所有能更新的点q.pop();vis[x]=0;for(int i=head[x];i!=-1;i=edge[i].next){    //i是边的编号，dis[i]没有意义int y=edge[i].t;        //第i条边储存的点值if(dis[y]>dis[x]+edge[i].l){dis[y]=dis[x]+edge[i].l;    //能更新就更新if(!vis[y]){        //如果不在队列，放入队列，否则不用放q.push(y);vis[y]=1;}}}}if(dis[t]>=0x3f3f3f3f)return -1;    //返回return dis[t];}int main(){cin>>n>>m>>s>>t;memset(head,-1,sizeof(head));       //初始化head为-1，要放在addedge之前while(m--){int x,y,z;cin>>x>>y>>z;       //读入addedge(x,y,z);     //无向边，存两次addedge(y,x,z);}cout<

#include
using namespace std;
int m,n;
int cnt=0;
int in[1005],head[1005];        //储存第i个点的入度和  链的第一个点的edge编号
struct ty{int t;          //储存和i相连的点int next;       //链式储存指针，指向下一个相邻点的edge编号
}edge[1005];        //第i个点相连的点，用链式前向星储存
void addedge(int x,int y){edge[++cnt].t=y;edge[cnt].next=head[x];head[x]=cnt;
}
vectortmp;
queueq;
void tuopu(){for(int i=1;i<=n;i++){if(in[i]==0)q.push(i);}int ans=0;while(!q.empty()){int x=q.front();q.pop();ans++;for(int i=head[x];i!=(-1);i=edge[i].next){in[edge[i].t]--;if(in[edge[i].t]==0)q.push(edge[i].t);}tmp.push_back(x);}if(ans!=n)cout<<-1;else{for(auto it:tmp){cout<>n>>m;memset(head,-1,sizeof(head));while(m--){int x,y;cin>>x>>y;addedge(x,y);in[y]++;}tuopu();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！