Java教程

单源最短路问题复习

本文主要是介绍单源最短路问题复习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在学习单源最短路之前,首先要了解数组和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

这篇关于单源最短路问题复习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!