二：最短路算法分析报告
背景
最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
单源最短路径
包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 。
求解单源最短路径问题可以采用Dijkstra算法，时间复杂度为O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配对堆等支持Decrease-Key操作的数据结构来进一步优化，优化后的时间复杂度为O(|E|+|V|log|V|)。
Dijkstra只可求无负权的最短路径，因为其目光短浅，看不到后面可以消减的量。在正数中容易得证，若a<b，Dijkstra会取a，若再有一条路c，a+c<b+c是正确的。但引入负数后，可能会出现以下情况
，Dijkstra会先选择A-B这条边，此时A->B的距离固定为1，不再改变，但其实A->B最短路是-1，虽然A->C的最短路是正确的，为-2，但这样的算法是不可使用的。
如果图中有负权回路，可以采用Bellman-Ford算法，算法复杂度是O(|V||E|)。但Bellman-ford算法浪费了许多时间做无必要的松弛，可用SPFA算法进行优化，SPFA算法是用队列进行的优化，优化后时间复杂度为O(k|E|)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2，由此可见该优化的效果十分显著。
全局最短路径
求图中所有的最短路径可以采用Floyd-Warshall算法，算法时间复杂度为O(|V|^3)。对于稀疏图，还可采用Johnson算法，其采用Bellman-ford和Dijkstra作为其子函数，时间复杂度为O（VElgV）。二者都可计算含负权路径的图，但不可含有负环。
两点最短路径
即已知起点和终点，求两结点之间的最短路径。通常可以用广度优先搜索（BFS）、深度优先搜索（DFS）等方式来实现，时间复杂度是O(|V|)。
本篇报告分析dijkstra算法和floyd算法。
问题描述
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
基本要求
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。
测试数据
输入
6 10
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 4 3
3 5 1
3 6 5
4 5 1
5 6 2
0 0
输出
4
算法思想
一：dijkstra
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。
在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
二：floyd
（1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值，否则为。
（2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。
（3）所有顶点试探完毕，算法结束。
实现过程
一：dijkstra
|
终点 |
从V1到各终点的最短路径及长度 |
|||||
|
V2 |
2 <V1,V2> |
2 <V1,V2> |
------- |
------ |
-------- |
------- |
|
V3 |
5 <V1,V3> |
4 <V1,V4,V3> |
4 <V1,V4,V3> |
3 <V1,V4,V5,V3> |
------- |
--------- |
|
V4 |
1 <V1,V4> |
---------- |
------- |
-------- |
------- |
--------- |
|
V5 |
INF |
2 <V1,V4,V5> |
2 <V1,V4,V5> |
--------- |
------ |
-------- |
|
V6 |
INF |
INF |
INF |
4 <V1,V4,V5,V6> |
4 <V1,V4,V5,V6> |
-------- |
|
|
V4:1 <V1,V4> |
V2:2 <V1,V2> |
V5:2 <V1,V4,V5> |
V3:3 <V1,V4,V5,V3> |
V6:4 <V1,V4,V5,V6> |
|
图用带权邻接矩阵存储map[][]
数组dis[]存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值。
数组vis[]表示从是否访问过此点。
二：floyd
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。
初始
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
5 |
1 |
INF |
INF |
|
2 |
2 |
0 |
3 |
2 |
INF |
INF |
|
3 |
5 |
3 |
0 |
3 |
1 |
5 |
|
4 |
1 |
2 |
3 |
0 |
1 |
INF |
|
5 |
INF |
INF |
1 |
1 |
0 |
2 |
|
6 |
INF |
INF |
5 |
INF |
2 |
0 |
加入1
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
5 |
1 |
INF |
INF |
|
2 |
|
0 |
3 |
2 |
INF |
INF |
|
3 |
|
|
0 |
3 |
1 |
5 |
|
4 |
|
|
|
0 |
1 |
INF |
|
5 |
|
|
|
|
0 |
2 |
|
6 |
|
|
|
|
|
0 |
加入2
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
5 |
1 |
INF |
INF |
|
2 |
|
0 |
5 |
2 |
INF |
INF |
|
3 |
|
|
0 |
3 |
1 |
5 |
|
4 |
|
|
|
0 |
1 |
INF |
|
5 |
|
|
|
|
0 |
2 |
|
6 |
|
|
|
|
|
0 |
加入3
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
5 |
1 |
INF |
10 |
|
2 |
|
0 |
5 |
2 |
4 |
8 |
|
3 |
|
|
0 |
3 |
1 |
5 |
|
4 |
|
|
|
0 |
1 |
8 |
|
5 |
|
|
|
|
0 |
2 |
|
6 |
|
|
|
|
|
0 |
加入4
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
4 |
1 |
2 |
9 |
|
2 |
|
0 |
3 |
2 |
3 |
8 |
|
3 |
|
|
0 |
3 |
1 |
5 |
|
4 |
|
|
|
0 |
1 |
8 |
|
5 |
|
|
|
|
0 |
2 |
|
6 |
|
|
|
|
|
0 |
加入5
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
2 |
3 |
1 |
2 |
4 |
|
2 |
|
0 |
3 |
2 |
3 |
5 |
|
3 |
|
|
0 |
2 |
1 |
3 |
|
4 |
|
|
|
0 |
1 |
3 |
|
5 |
|
|
|
|
0 |
2 |
|
6 |
|
|
|
|
|
0 |
代码实现
一：dijkstra
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
int pri[][];//两个顶点之间距离
int dis[];//起点到该点的最短距离
int vis[];//标记数组
int n,m; void dijkstra()
{
memset(vis,,sizeof(vis));
vis[]=;
for(int i=;i<=n;i++)
dis[i]=pri[][i];
for(int i=;i<n;i++)
{
int M=INF,k=-;
//每次找出最小的距离加入到集合
for(int j=;j<=n;j++)
{
if(!vis[j]&&dis[j]<M)
M=dis[j],k=j;
}
if(k==-)
return ;
vis[k]=;//加入集合
//新加入一个顶点，更新到达各个顶点的距离
for(int j=;j<=n;j++)
if(!vis[j]&&dis[j]>dis[k]+pri[k][j])
dis[j]=dis[k]+pri[k][j];
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,n||m)
{
//初始化
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
pri[i][j]=i==j?:INF;
for(int i=;i<=m;i++)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(pri[a][b]>c)//防止重边
pri[a][b]=pri[b][a]=c;//这个是无向图的存储
}
dijkstra();
printf("%d\n",dis[n]);
}
return ;
}
二：floyd
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
int pri[][];//两个顶点之间距离
int dis[];//起点到该点的最短距离
int vis[];//标记数组
int n,m;
void floyd()
{
for(int k=;k<=n;k++)//中间点
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
pri[i][j]=min(pri[i][j],pri[i][k]+pri[k][j]);//取当前最短距离和含有中间顶点的距离的最小值
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,n||m)
{
//初始化
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
pri[i][j]=i==j?:INF;
for(int i=;i<=m;i++)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(pri[a][b]>c)//防止重边
pri[a][b]=pri[b][a]=c;//这个是无向图的存储
}
floyd();
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",pri[a][b]);
}
return ;
}
运行截图
一：dijkstra
二：floyd
个人总结
Dijkstra算法的时间复杂度为O(n^2) ,较之Floyd算法有很大提升，但是由于使用的是邻接矩阵的存储，所以说当顶点数过大的时候，我们就不可能用二维数组来存储了。切记每次加入一个点时要更新最短距离。Floyd算法的时间复杂度为（n^3），虽然代码简单但当n很大时会超时。