最短路径Dijkstra算法--求距离和路径

1、题目描述 求单条路线

2、AC代码

#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
typedef long long ll;
const int N=105;
int n,m,s,t;

struct node
{
	int v; // 边终点
	int w;// 边权
	node(int x,int y):v(x),w(y){
	}
};
vector<node> adj[N];
int d[N],pre[N];
bool vis[N];
void dijk(int S)
{
	fill(d,d+N,inf);
	//fill(num,num+N,0);
	d[S]=0;
	
	for(int i=0;i<n;i++)
	{
		int u=-1,min=inf;
		for(int j=0;j<n;j++)
		{
			if(!vis[j] && d[j] < min)
			{
				min=d[j];
				u=j;
			}
		}
		if(u==-1)return;
		vis[u]=true;
		for(int j=0;j<(int)adj[u].size();j++)
		{
			int v = adj[u][j].v; // 获取边的终点 
			if(!vis[v])
			{
				if(d[u] + adj[u][j].w < d[v])
				{
					d[v] = d[u] + adj[u][j].w;
					pre[v] = u; //记录v的前驱
				}
			}
		}
	}
}
// 递归输出路径
void dfs(int v)
{
	if(v==s)
	{
		cout<<s<<"->";
		return;
	}
	dfs(pre[v]);
	cout<<v;
	if(v!=t)
	{
		cout<<"->";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	
	cin>>n>>m>>s>>t;
	int u,v,w;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>w;
		adj[u].push_back(node(v,w));
		adj[v].push_back(node(u,w));
	}
	dijk(s);
	
	cout<<d[t]<<" ";
	dfs(t);
  	return 0;
}

2、求多条路线

#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
typedef long long ll;
const int N=105;
int n,m,s,t;

struct node
{
	int v; // 边终点
	int w;// 边权
	node(int x,int y):v(x),w(y){
	}
};
vector<node> adj[N];
int d[N];
bool vis[N];
vector<int> pre[N]; //记录前驱
vector<int> tpath; // 记录当前的路径
vector<vector<int>> paths; //记录所有最短路径 
void dijk()
{
	fill(d,d+N,inf);
	d[s]=0;
	
	for(int i=0;i<n;i++)
	{
		int u=-1,min=inf;
		for(int j=0;j<n;j++)
		{
			if(!vis[j] && d[j] < min)
			{
				min=d[j];
				u=j;
			}
		}
		if(u==-1)return;
		vis[u]=true;
		for(int j=0;j<(int)adj[u].size();j++)
		{
			int v = adj[u][j].v; // 获取边的终点 
			int w = adj[u][j].w;
			if(!vis[v])
			{
				if(d[u] + w < d[v])
				{
					d[v] = d[u] + w;
					pre[v].clear(); // 因为有更优的路径，所以清空之前的
					pre[v].push_back(u); // 记录v的前驱u 
				}else if(d[u] + w == d[v])
				{
					pre[v].push_back(u);
				}
			}
		}
	}
}
void dfs(int v)
{
	if(v==s) // 到达起点 
	{
		tpath.push_back(v); // 当前路线添加上起点 
		paths.push_back(tpath); // 记录当前路线信息
		tpath.pop_back(); //清空当前路线的起点 
		return;
	}
	tpath.push_back(v);
	for(int i=0;i<(int)pre[v].size();i++)
	{
		dfs(pre[v][i]);
	}
	tpath.pop_back(); //清空当前路线 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	
	cin>>n>>m>>s>>t;
	int u,v,w;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>w;
		adj[u].push_back(node(v,w));
		adj[v].push_back(node(u,w));
	}
	dijk();
	dfs(t);
	cout<<paths.size()<<endl;
	for(int i=0;i<paths.size();i++)
	{
		reverse(paths[i].begin(),paths[i].end()); // 因为每一条路线信息是倒过来的，所以需要先逆序 
	}
	sort(paths.begin(),paths.end()); // 对所有路线进行排序
	for(int i=0;i<paths.size();i++)
	{
		for(int j=0;j<paths[i].size();j++)
		{
			cout<<paths[i][j];
			if(j<paths[i].size()-1)cout<<"->";
		}
		cout<<endl;
	} 
  	return 0;
}