在学习单源最短路之前，首先要了解数组和for循环

• for循环

for循环，顾名思义就是循环语句

运行以下代码

#include<iostream>
#include<cstring>
using namespace std;
int main(){
    for(int i=0;i<=10;i++){
        cout<<i<<' ';
    }
    return 0;
}

得到

 

 

 运行以下代码

#include<iostream>
#include<cstring>
using namespace std;
int main(){
    for(int i=0;i<=10;i++){
        cout<<i<<endl;
        for(int j=0;j<=10;j++){    
          cout<<j<<' ';
        }
        cout<<endl;
    }
    return 0;
}

得到

 

 

 这两个例子可以直观地理解for循环的运行方式和效果

• 数组

对于一维数组，形式上可以理解为一个数值可变的数列

对于二维数组，形式上可以理解为一个矩阵

其作用是有序地储存变量，

例子如下

#include<iostream>
#include<cstring>
using namespace std;
int main(){
    int a[10][10];//声明一个10*10的二维数组，仅做储存数据使用，无数学意义 
    memset(a,127,sizeof(a));//将数组中的所有元素全赋值为2139062143
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }//for循环输出 
    return 0; 
}

运行后输出结果

 需要注意的是，数组的下标从0开始计算；

如：a[10]中包含的元素为a[0]~a[9]

但是在处理问题的时候通常忽略掉a[0]，从a[1]开始初始化

• 单源最短路问题介绍

 

对于如图所示的图，字母表示节点，也即地点，其中相连的边表示两点间的距离

单源最短路问题是指以一个节点为起点，求它到其余每个点的最短距离

• 图的存储方式

在输入时，第一行为n，m，s三个数字，分别表示该图的点数和边数，以及起点；目标是求该起点到其余各点的最短路径

之后m行，每行的第一个数字为该边的起点编号，第二个数字为终点编号，第三个数字为该边的长度

eg：

 

 

 

 

 

 

我们以数组dis[]表示起点s到每个点的路径长度

初始化时令dis[s]=0

dis[i]=2147483647,其中i<=n且i!=s

（dis[s]即s到自身的距离，为0；而开始时，s到其余各点的距离未知，设为不可到达，用一个很大的数表示即可）

以数组u[],v[],w[],分别表示边i的起点，终点，长度(w表示weight，权重）

则可有以下的输入代码

        int n,m,s,u[500001],v[500001],w[500001]
        cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        }
    for(int i=1;i<=n;i++)
        dis[i]=2147483647；
        dis[s]=0;

至此，整个图储存完毕

• 求起点s到所有点的最短路径

比较好理解的：若存在边(u[j],v[j],w[j])使得dis[v[j]]>dis[u[j]]+w[j]

则说明起点s先到u[j]再到v[j]比s直接到v[j]更快

则令dis[v[j]]=dis[u[j]]+w[j]，保证最小

要进行上述操作，则只需运行如下代码

for(int j=1;j<=m;j++){
       if(dis[v[j]]>dis[u[j]]+w[j]){
               dis[v[j]]=dis[u[j]]+w[j];
           }
       }

如果只进行一次上述操作，那么dis[]中存储的结果只会是和s相邻的边（可以在纸上手动运行以下代码），其余边没有进行迭代

为了让除s外的n-1个点都被遍历到，我们需要进行n-1次上述操作，即

for(int i=1;i<=n-1;i++){//该外层i循环在这里只是个计数作用 
	        for(int j=1;j<=m;j++){
	            if(dis[v[j]]>dis[u[j]]+w[j]){
	                dis[v[j]]=dis[u[j]]+w[j];
	            }
	        }
	}

至此，dis[i]中的数均变为s到i点的最短路径

最后输出即可

    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;

 

优化先不谈

总体代码如下：

#include<bits/stdc++.h>
using namespace std;
int u[500001],v[500001],w[500001];
long long dis[500001];
int n,m,s;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
        dis[i]=2147483647;
        dis[s]=0;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
    }
    for(int i=1;i<=n-1;i++){
            for(int j=1;j<=m;j++){
                if(dis[v[j]]>dis[u[j]]+w[j]){
                    dis[v[j]]=dis[u[j]]+w[j];
                }
            }
    }
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}

将上述例子中的数代入计算一下（用手）

得到可以输出dis数组是

0 2 4 3

算法时间复杂度为O（n*m），非常慢，当n*m比较大时计算机无法承受

 

end