12月13日星期六9:00-12:00
Dijkstra(迪杰斯特拉)求最短路径
S+03L01【入门】最短路径
描述
在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。
输入描述
输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。（2≤s<n≤50）
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值（0≤权值≤100）；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
输出描述
只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
请注意行尾输出换行。
用例输入 1
4 2
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
用例输出 1
6 4 7
提示
在本题中，需要按照题目描述中的算法完成迪杰斯特拉算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每个可达顶点的最短路径之后，算法才能够结束。
迪杰斯特拉算法的特点是按照路径长度递增的顺序，依次添加下一条长度最短的边，从而不断构造出相应顶点的最短路径。
另外需要注意的是，在本题中为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。
代码
#include<bits/stdc++.h>
using namespace std;
int n,s;
int num[510][510];//邻接矩阵
int d[510];//从起点到该点的最短路径长度是多少
int f[510];
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>num[i][j];
}
}
memset(d,0x3f,sizeof(d));
d[s]=0;
for(int i=1;i<=n;i++){
int mi = -1;
//寻找不确定点里面权值最小的那个点 v
for(int j=1;j<=n;j++){
if(!f[j]&&(mi==-1||d[mi]>d[j])){
mi = j;
}
}
f[mi]=true;
//更新mi点能到的点的最小距离
for(int j=1;j<=n;j++){
if(num[mi][j]!=0&&d[mi]+num[mi][j]<d[j]){
d[j] = d[mi]+num[mi][j];
}
}
}
for(int i=1;i<=n;i++){
if(i!=s){
if(d[i]!=0x3f3f3f3f){
cout<<d[i]<<" ";
}else{
cout<<-1<<" ";
}
}
}
return 0;
}
S+03L02【基础】最短距离和路径问题
描述
有n个城市（编号为1~n），m条道路（n<1000, m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离和经过的城市名。
输入描述
第一行输入四个数，分别为n，m，s，t。（n<1000, m<10000，1≤s,t≤n）
接下来m行，每行三个数x，y，len，分别为两个城市名和距离。（1≤x,y≤n，1≤len≤50000）
输出描述
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can't arrive”。
请注意：本题两个相同的城市之间可能存在多条路径。
用例输入 1
3 3 1 3
1 3 3
1 2 1
2 3 1
用例输出 1
2
1 2 3
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int num[510][510];//邻接矩阵
int d[510];//从起点到该点的最短路径长度是多少
int f[1100];
int r[11000];
void print(int x){
if(r[x]!=0){
print(r[x]);
}
cout<<x<<" ";
}
int main(){
cin>>n>>m>>s>>t;
memset(d,0x3f,sizeof(d));
memset(num,0x3f,sizeof(num));
for(int i=1;i<=m;i++){
int q,w,x;
cin>>q>>w>>x;
if(num[q][w]>x){
num[q][w]=x;
num[w][q]=x;
}
}
d[s]=0;
for(int i=1;i<=n;i++){
int mi = -1;
//寻找不确定点里面权值最小的那个点
for(int j=1;j<=n;j++){
if(!f[j]&&(mi==-1||d[mi]>d[j])){
mi = j;
}
}
f[mi]=true;
//更新mi点能到的点的最小距离
for(int j=1;j<=n;j++){
if(num[mi][j]!=0x3f3f3f3f&&d[mi]+num[mi][j]<d[j]){
d[j] = d[mi]+num[mi][j];
r[j] = mi;
}
}
}
if(d[t]!=0x3f3f3f3f){
cout<<d[t]<<endl;
print(t);
}else{
cout<<"can't arrive";
}
return 0;
}