在最短路径问题中,迪杰斯特拉算法是比较简单算法,在了解之前,先要了解邻接矩阵的定义.
在最短路径问题中,首要的就是要把题目所描述的图存进来,邻接矩阵就是用一个二维数组储存这个图.分别把两个节点作为横纵坐标,把长度储存在这个坐标点内.例如一段为,2,3,4,表示2,3两个点相连接的长度为4,所以用map[2][3]把4存起来,值得注意的是方向,因为是二维数组,如果2到3为4,那么map[2][3]=4,而3到2长度为5,那么map[3][2]=5.题目强调双向那么map[a][b]=map[b][a].
然后就是迪杰斯特拉算法的思想,抽象的讲,迪杰斯特拉算法就是用一个数组把从起点到每个点最短路径存起来,比如dist[i]就等于从起点到点i的距离.它会遍历所有点若干次,不断更新dist里面的值,直到到达目的地,我们画一个图看,举个例子.
Problem Description
某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
Input
本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
题目来自:杭电oj
首先我们针对第一组数据存图:
因为题目说是双向,所以就对称分布,对角线上那一条无意义,如果没有连通或者横纵坐标相等,都可以用一个很大的数代替.然后就是我的代码:
#include<iostream> using namespace std; #define inf 0x7FFFFFFF//定义一个正无穷量词 #define M 201 int Map[M][M],Dist[M],visit[M]; //map为邻接矩阵,存图;dist为到某点最短路径;visit为当前城市最短距离是否求出. int main(){ int m,n,a,b,dis,start,Min,next,targe; while(scanf("%d%d",&n,&m)==2){ //输入两个数,n为城镇数,m为路数 for(int i=0;i<n;i++){ visit[i]=1;//标记初始化为1 Dist[i]=inf;// for(int j=0;j<n;j++)Map[i][j]=inf;//初始化无穷大 } while(m--){ scanf("%d%d%d",&a,&b,&dis); Map[a][b]=min(Map[a][b],dis); Map[b][a]=Map[a][b];//存图 } scanf("%d%d",&start,&targe);//输入起点终点 Dist[start]=0; visit[start]=0;//标记 while(start!=targe){//一直找到起点到终点 Min=inf; for(int i=0;i<n;i++){//从起点向所以其他城镇出发 if(Map[start][i]!=inf) Dist[i]=min(Dist[i],Map[start][i]+Dist[start]); //如果已经连接,松弛操作,Dist表示已经存了的i最短路径 //Map[start][i]+Dist[start]表示由此点出发到i的路径 if(visit[i]!=0&&Dist[i]<Min){ //已经求出到i最短路径,并且存在 next=i;//存为下一个起点 Min=Dist[i];//min为到该点最短路径 } } if(Min==inf)break;//如果最短没有连接,跳过 start=next;//定义这次终点为下一个起点 visit[start]=0;//开始下一个循环找,并且标记 } if(Dist[targe]==inf)printf("-1\n"); else{ printf("%d\n",Dist[targe]); } } }
如图的注释,不断更新dist数组值,保留此时的最小路,因为下一条路最短路要么是从这一条的最小路出发,或者直接到达这个点,直接到达则不更新,如果从上一条的最短继续前进,那么核心代码就是
Dist[i]=min(Dist[i],Map[start][i]+Dist[start]);
,这就是松弛操作,举个例子,我们从1到4要走20的路程,而从1到2再到4要走10,将两者比较,选择小的,这就是将dist更新的原理.