最短路径问题(python实现)
解决最短路径问题：(如下三种算法)
(1)迪杰斯特拉算法(Dijkstra算法)
(2)弗洛伊德算法(Floyd算法)
(3)SPFA算法
第一种算法：
Dijkstra算法
广度优先搜索解决赋权有向图或者无向图的单源最短路径问题.是一种贪心的策略
算法的思路
声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点s的路径权重被赋为0(dis[s]=0)。若对于顶点s存在能直接到达的边(s,m)，则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，再看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值，然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
第二种算法：
Floyd算法
原理：
Floyd算法(弗洛伊德算法)是一种在有向图中求最短路径的算法。它是一种求解有向图中点与点之间最短路径的算法。
用在拥有负权值的有向图中求解最短路径(不过不能包含负权回路)
流程：
有向图中的每一个节点X，对于图中过的2点A和B，
如果有Dis(AX)+ Dis(XB)< Dis(AB)，那么使得Dis(AB)=Dis(AX)+Dis(XB)。
当所有的节点X遍历完后，AB的最短路径就求出来了。
示例一：
#-*- coding:utf-8 -*-
#python实现Floyd算法
N = 4
_=float('inf')   #无穷大
graph = [[ 0, 2, 6, 4],[ _, 0, 3, _],[ 7, _, 0, 1],[ 5, _,12, 0]]
path = [[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1]]    #记录路径，最后一次经过的点
def back_path(path,i,j):      #递归回溯
while(-1 != path[i][j]):
back_path(path,i,path[i][j])
back_path(path,path[i][j],j)
print path[i][j],14
return;
return;
print "Graph:\n",graph
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
path[i][j] = k
print "Shortest distance:\n",graph
print "Path:\n",path
print "Points pass-by:"
for i in range(N):
for j in range(N):
print "%d -> %d:" % (i,j),
back_path(path,i,j)
print "\n",
示例二：
#!usr/bin/env python#encoding:utf-8
'''
功能：使用floyd算法求最短路径距离
'''
import random
import time
def random_matrix_genetor(vex_num=10):
'''
随机图顶点矩阵生成器
输入：顶点个数，即矩阵维数
'''
data_matrix=[]
for i in range(vex_num):
one_list=[]
for j in range(vex_num):
one_list.append(random.randint(1, 100))
data_matrix.append(one_list)
return data_matrixdef floyd(data_matrix):
'''
输入：原数据矩阵，即：一个二维数组
输出：顶点间距离  '''
dist_matrix=[]
path_matrix=[]
vex_num=len(data_matrix)
for h in range(vex_num):
one_list=['N']*vex_num
path_matrix.append(one_list)
dist_matrix.append(one_list)
for i in range(vex_num):
for j in range(vex_num):
dist_matrix=data_matrix
path_matrix[i][j]=j
for k in range(vex_num):
for i in range(vex_num):
for j in range(vex_num):
if dist_matrix[i][k]=='N' or dist_matrix[k][j]=='N':
temp='N'
else:
temp=dist_matrix[i][k]+dist_matrix[k][j]
if dist_matrix[i][j]>temp:
dist_matrix[i][j]=temp
path_matrix[i][j]=path_matrix[i][k]
return dist_matrix, path_matrixdef main_test_func(vex_num=10):
'''
主测试函数
'''
data_matrix=random_matrix_genetor(vex_num)
dist_matrix, path_matrix=floyd(data_matrix)
for i in range(vex_num):
for j in range(vex_num):
print '顶点'+str(i)+'----->'+'顶点'+str(j)+'最小距离为:', dist_matrix[i][j]
if __name__ == '__main__':
data_matrix=[['N',1,'N',4],[1,'N',2,'N'],['N',2,'N',3],[4,'N',3,'N']]
dist_matrix, path_matrix=floyd(data_matrix)
print dist_matrix
print path_matrix
time_list=[]
print '------------------------------节点数为10测试情况------------------------------------'
start_time0=time.time()
main_test_func(10)
end_time0=time.time()
t1=end_time0-start_time0
time_list.append(t1)
print '节点数为10时耗时为：', t1
print '------------------------------节点数为100测试情况------------------------------------'
start_time1=time.time()
main_test_func(100)
end_time1=time.time()
t2=end_time1-start_time1
time_list.append(t2)
print '节点数为100时耗时为：', t2
print '------------------------------节点数为1000测试情况------------------------------------'
start_time1=time.time()
main_test_func(1000)
end_time1=time.time()
t3=end_time1-start_time1
time_list.append(t3)
print '节点数为100时耗时为：', t3
print '--------------------------------------时间消耗情况为：--------------------------------'
for one_time in time_list:
print one_time
示例三：
import numpy as np
Max   = 100
v_len  = 4
edge  = np.mat([[0,1,Max,4],[Max,0,9,2],[3,5,0,8],[Max,Max,6,0]])
A    = edge[:]
path  = np.zeros((v_len,v_len))
def Folyd():
for i in range(v_len):
for j in range(v_len):
if(edge[i,j] != Max and edge[i,j] != 0):
path[i][j] = i
print 'init:'
print A,'\n',path
for a in range(v_len):
for b in range(v_len):
for c in range(v_len):
if(A[b,a]+A[a,c]
A[b,c] = A[b,a]+A[a,c]
path[b][c] = path[a][c]
print 'result:'
print A,'\n',path
if __name__ == "__main__":
Folyd()
第三种算法：
SPFA算法是求解单源最短路径问题的一种算法，由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。
其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。
思路：
我们用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

【例9.5】城市交通路网

时间限制: 1000 ms         内存限制: 65536 KB
 

【题目描述】
下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

如图：求v1到v10的最短路径长度及最短路径。
【输入】
第一行为城市的数量N;
后面是N*N的表示两个城市间费用组成的矩阵。
【输出】
A->E的最省费用。
【输入样例】


10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0


【输出样例】


minlong=19
1 3 5 8 10


【来源】





#include<iostream>
#include<cstring>
#define MAXN 100
using namespace std;
int a[MAXN+5][MAXN+5];//a[i][x]表示vi到vx的最短距离 
int f[MAXN+5];//f[i]表示点vi到v10的最短距离 
int suf[MAXN+5];//suf[i]=x;表示i的后缀节点为x 
int main()
{
	memset(a,0,sizeof(a));
	memset(suf,0,sizeof(f)); 
	int i,x,n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int x=1;x<=n;x++)
		{
			cin>>a[i][x];
		}
		f[i]=100000;
	} 
	f[n]=0;
	for(int i=n-1;i>=1;i--)
	{
		for(int x=i+1;x<=n;x++)
		{
			if((a[i][x]>0)&&(f[x]!=100000)&&(f[i]>a[i][x]+f[x]))
			//如果vi到vx之间有路径，vx到v10有路径，并且vi直接到v10的路径大于通过vx中转的路径 
			{
				f[i]=a[i][x]+f[x];
				suf[i]=x;//i节点的后缀节点为x 
			}
		}
	}
	x=1;
	cout<<"minlong="<<f[1]<<endl;
	while(x!=0)//模拟循环链表 
	{
		cout<<x<<" ";
		x=suf[x];
	}
	cout<<endl;
	return 0;
}
 

说明：自己在学习动态规划的过程中，碰到求解最短路径问题的实例，而理解了动态规划之后，再理解实例中的逐段累加法可能会让人难以理解。这篇文章主要是对比枚举法、逐段累加法、动态规划法求解最短路径问题的思路以及加法次数

问题：两点之间连线上的数字表示距离，求由A到G的最短路径（问题很常见，不过多描述了）



（图片来源：《运筹学·第三版》清华大学出版社）

为了说明的方便，这里删去图上的EFG节点，只保留A到D节点



这里，从A到D一共有2*3*2 = 12条路径，下面是加法运算次数对比：

 

法一. 普通计算，枚举法

思路：每条路径是单独计算的，例如：A到B1到C1到D1这条路径，先计算AB1 + B1C1，之后，AB1 + B1C1的和与C1D1相加。

一共12条路径，每条路径上有2次

12*2 = 24次

分别是

AB1 + B1C1 与 AB1C1长度 + C1D1

AB1 + B1C1 与 AB1C1长度 + C1D2

AB1 + B1C2 与 AB1C2长度 + C2D1

AB1 + B1C2 与 AB1C2长度 + C2D2

AB1 + B1C3 与 AB1C3长度 + C3D2

AB1 + B1C3 与 AB1C3长度 + C3D3

AB2 + B2C2 与 AB2C2长度 + C2D1

AB2 + B2C2 与 AB2C2长度 + C2D2

AB2 + B2C3 与 AB2C3长度 + C3D2

AB2 + B2C3 与 AB2C3长度 + C3D3

AB2 + B2C4 与 AB2C4长度 + C4D2

AB2 + B2C4 与 AB2C4长度 + C4D3

 

法二. 逐段累加法（当理解了动态规划之后，可能会觉得逐段累加不好理解）

思路：先计算所有的A到C的路径长度，并保存，再计算所有的A到D的路径长度，而A到D的路径中包含了一部分已经计算且保存了的A到C的路径，那么这部分就直接调用保存的结果而无需再次计算（以此类推，如果是ABCDE，先计算所有的A到C的路径长度，再计算所有的A到D的路径长度，再计算所有的A到E的路径长度，这就是逐段累加的含义）

先计算A到C，6条路径，每条路径1次加法，一共6次加法

AB1 + B1C1

AB1 + B1C2

AB1 + B1C3

AB2 + B2C1

AB2 + B2C2

AB2 + B2C3

并且这六个结果都保存

再计算A到D，12条路径，每条路径都分为A到C与C到D两部分来看，A到C的路径长度已经计算过且保存了结果，所以对于每条路径来说，只需计算这条路所经过的A到C的路径长度 + 这条路径所经过的CD长度。每条路径都只有1次加法，一共12次加法

分别是

AB1C1长度 + C1D1

AB1C1长度 + C1D2

AB1C2长度 + C2D1

AB1C2长度 + C2D2

AB1C3长度 + C3D2

AB1C3长度 + C3D3

AB2C2长度 + C2D1

AB2C2长度 + C2D2

AB2C3长度 + C3D2

AB2C3长度 + C3D3

AB2C4长度 + C4D2

AB2C4长度 + C4D3

6 + 12 = 18次

可以看出，逐段累加方法相对于枚举法的优势在于，保存所有的逐段累加的计算结果，供之后的计算直接调用

 

法三. 动态规划法

思路：逆向寻找最短路径，为了和上面两种方法对比，这里以D为起点，A为终点。先计算所有的C到A的路径长度，并保存，而且选出所有的C到A的最短路径长度，再计算所有的D到A的路径长度，而D到A的路径中包含了一部分已经计算、保存且选出的C到A的最短路径，那么这部分就直接调用保存的结果而无需再次计算（以此类推，如果是ABCDE，先计算所有的C到A的路径长度，选出所有的C到A的最短路径长度，再计算所有的D到A的路径长度，选出所有的D到A的最短路径长度，再计算所有的E到A的路径长度）

先计算C到A，6条路径，每条路径1次加法，一共6次加法

AB1 + B1C1

AB1 + B1C2

AB1 + B1C3

AB2 + B2C1

AB2 + B2C2

AB2 + B2C3

并且这六个结果都保存，且选出

C1到A的最短路径长度，AB1C1

C2到A的最短路径长度，AB1C2

C3到A的最短路径长度，AB2C3

C4到A的最短路径长度，AB2C4

再计算D到A，每条D到A的路径都分为D到C与C到A两部分来看，C到A的路径长度已经计算过且保存了结果，且选出了最短路径，所以不必考虑每条C到A的路径，只用考虑C到A的最短路径，而D到C有8条路径，可以认为当从D到达C时直接选用C到A的最短路径到达A。所以，实际上D到A只需要考虑8条路径，对于这8条路径中的每条路径来说，需要计算的是这条路所经过的DC长度 + C到A的最短路径长度。每条路径都只有1次加法，一共8次加法

分别是

AB1C1长度 + C1D1

AB1C1长度 + C1D2

AB1C2长度 + C2D1

AB2C2长度 + C2D2

AB2C3长度 + C3D2

AB2C3长度 + C3D3

AB2C4长度 + C4D2

AB2C4长度 + C4D3

6 + 8 = 14次

可以看出，动态规划相对于逐段累加方法的优势在于，计算D到A的最短路径时，直接取用C到A的最短路径，而不是考虑C到A的全部路径

 

三种方法结合起来对比


			
 
			
			

			
枚举法
			
			

			
逐段累加法
			
			

			
动态规划法
			
		

			
加法次数
			
			

			
24
			
			

			
18
			
			

			
14
			
		

			
具体加法
			
			

			
AB1 + B1C1

			
AB1 + B1C1

			
AB1 + B1C2

			
AB1 + B1C2

			
AB1 + B1C3

			
AB1 + B1C3

			
AB2 + B2C2

			
AB2 + B2C2

			
AB2 + B2C3

			
AB2 + B2C3

			
AB2 + B2C4

			
AB2 + B2C4

			
AB1C1长度 + C1D1

			
AB1C1长度 + C1D2

			
AB1C2长度 + C2D1

			
AB1C2长度 + C2D2

			
AB1C3长度 + C3D2

			
AB1C3长度 + C3D3

			
AB2C2长度 + C2D1

			
AB2C2长度 + C2D2

			
AB2C3长度 + C3D2

			
AB2C3长度 + C3D3

			
AB2C4长度 + C4D2

			
AB2C4长度 + C4D3
			
			

			
AB1 + B1C1

			
AB1 + B1C1（省掉）

			
AB1 + B1C2

			
AB1 + B1C2（省掉）

			
AB1 + B1C3

			
AB1 + B1C3（省掉）

			
AB2 + B2C2

			
AB2 + B2C2（省掉）

			
AB2 + B2C3

			
AB2 + B2C3（省掉）

			
AB2 + B2C4

			
AB2 + B2C4（省掉）

			
AB1C1长度 + C1D1

			
AB1C1长度 + C1D2

			
AB1C2长度 + C2D1

			
AB1C2长度 + C2D2

			
AB1C3长度 + C3D2

			
AB1C3长度 + C3D3

			
AB2C2长度 + C2D1

			
AB2C2长度 + C2D2

			
AB2C3长度 + C3D2

			
AB2C3长度 + C3D3

			
AB2C4长度 + C4D2

			
AB2C4长度 + C4D3
			
			

			
AB1 + B1C1

			
AB1 + B1C1（省掉）

			
AB1 + B1C2

			
AB1 + B1C2（省掉）

			
AB1 + B1C3

			
AB1 + B1C3（省掉）

			
AB2 + B2C2

			
AB2 + B2C2（省掉）

			
AB2 + B2C3

			
AB2 + B2C3（省掉）

			
AB2 + B2C4

			
AB2 + B2C4（省掉）

			
AB1C1长度 + C1D1

			
AB1C1长度 + C1D2

			
AB1C2长度 + C2D1

			
AB1C2长度 + C2D2

			
AB1C3长度 + C3D2（省掉）

			
AB1C3长度 + C3D3（省掉）

			
AB2C2长度 + C2D1（省掉）

			
AB2C2长度 + C2D2（省掉）

			
AB2C3长度 + C3D2

			
AB2C3长度 + C3D3

			
AB2C4长度 + C4D2

			
AB2C4长度 + C4D3
			
		

    本文参考http://blog.csdn.net/ochangwen/article/details/50730937，
    1.定义概览

    Floyd-Warshall算法（Floyd-Warshall algorithm）又称为插点法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

    
    2.算法描述：

    1)算法思想原理：

     Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动 态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）， 从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设

Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径

短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

    2).算法描述：

        a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　

        b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

    3).Floyd算法过程矩阵的计算----十字交叉法

      

   补充其中用到的十字交叉法如下：
    先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k列和对角线上的元素是不发生改变的（对角线上都是0，因为一个顶点到自己的距离就是0，一直不变；而当k为中间点时，k到其他顶点（第k行）和其他顶点到k（第k列）的距离是不变的）。
    因此每一步中我们只需要判断4*4-3*4+2=6个元素是否发生改变即可,也就是要判断既不在第k行第k列又不在对角线上的元素。具体计算步骤如下：以k为中间点（1）“三条线”：划去第k行，第k列，对角线（2）“十字交叉法”：对于任一个不在三条线上的元素x，均可与另外在k行k列上的3个元素构成一个2阶矩阵，x是否发生改变与2阶矩阵中不包含x的那条对角线上2个元素的和有关，若二者之和小于x，则用它们的和替换x，对应的Path矩阵中的与x相对应的位置用k来替代。。。

    具体实例及代码如下所示：

/**
 * @Title: Floyd.java
 * @Package dynamicprogramming
 * @Description: TODO
 * @author peidong
 * @date 2017-6-13 上午9:23:39
 * @version V1.0
 */
package dynamicprogramming;

/**
 * @ClassName: Floyd
 * @Description: 弗洛伊德最短路径算法
 * @date 2017-6-13 上午9:23:39
 *
 */
public class Floyd {

    public static void shorestFloyd(){
        int MAX_VALUE = 65535;
        int[][] edgesMatrix ={{0, 5, MAX_VALUE, 7}, {MAX_VALUE, 0, 4, 2}, {3, 3, 0, 2}, {MAX_VALUE, MAX_VALUE, 1, 0}};
        int n = 4;//vertexSize; 结点个数
        int[][] tc = new int[n][n];  //保存从i到j的最短路径值
        int[][] p = new int[n][n];  //保存经过的中间结点

        //初始化tc,p
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                p[i][j] = -1;
                tc[i][j] = edgesMatrix[i][j]; //便矩阵
            }
        }

        //进行Floyd算法，从0到n-1所有可能进行遍历
        for(int x = 0; x < n; x++){  //x表示中间结点
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(tc[i][j] > tc[i][x] + tc[x][j]){
                        tc[i][j] = tc[i][x] + tc[x][j];
                        p[i][j] = x;
                    }
                }
            }
        }
        // 下面对获得的结果进行展示
        System.out.println("最短路径状态转移矩阵为：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(" " + tc[i][j]);
            }
            System.out.println();
        }
        System.out.println("对应的结点矩阵为：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(" " + p[i][j]);
            }
            System.out.println();
        }
//      System.out.println("+++++++++++++++++++++++++++++++++++");
       /* for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("输出i=" + i + "到j=" + j + "最短路径：");
                int k = p[i][j];
                if (k == -1) {
                    System.out.println("没有最短路径");
                } else {
                    System.out.print(" " + k);
                    while (k != j) {
                        k = p[k][j];
                        System.out.print(" " + k);
                    }
                    System.out.println(" "+k);
                    System.out.println();
                }
            }
        }  */
    }
    /**
     * @Title: main
     * @Description: 测试用例
     * @param args
     * @return void
     * @throws
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        shorestFloyd();
    }

}