什么是最短路径问题
扫描二维码
随时随地手机看文章
1. 最短路径概述
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
全局最短路径问题 - 求图中所有的最短路径。(摘自百度百科)。
2. 解决方法
用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。 最常用的路径算法有:
Dijkstra算法
A*算法
SPFA算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法
所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先,我们可以发现有这样一个事实:如果P是G中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路。
3.博客链接
1. 几种算法比较
2. 单元最短路径(Dijkstra算法)
4.农大ACM1030代码: 点击我链接 用邻接矩阵存储图信息,可求出源点到任意节点的最短距离。
#includeusing namespace std; int main() { //ifstream cin("1030.in"); int infinity=1000,j,i,n,k,t,**w,*s,*p,*d; //cout<<"input the value of n:"; cin >> n; //cout<<endl; d=new int[n]; s=new int[n]; p=new int[n]; w=new int*[n]; for(i=0;i<n;i++) {w[i]=new int[n];} //输入各路径的权值。。 for(i=0;i<n;i++) for(j=0;j>w[i][j]; for(s[0]=1,i=1;i<n;i++) { s[i]=0;d[i]=w[0][i]; if(d[i]<infinity) p[i]=0; else p[i]=-1; } for(i=1;i<n;i++) { t=infinity; k=1; //从还没进行过松弛操作的点中选出到源点距离最小的点k。。 for(j=1;j<n;j++) if((!s[j])&&(d[j]<t)){t=d[j];k=j;} s[k]=1;//point k join the S //进行松弛操作。。就是看能否通过k获得源点0到点j的更短的路径。。p[j]记录的是从0到j的最短路径中j的上一个点。。 for (j=1;jd[k]+w[k][j])) {d[j]=d[k]+w[k][j];p[j]=k;} } //cout<<"从源点到其它顶点的最短距离依次如下:"; cout << d[n-1] << endl; return 0; }