最短路算法有三种形态：Floyd算法，Shortset Path Fast Algorithm算法，Dijkstra算法。我个人打算分三次把这三个算法介绍完。今天先来介绍最简单的Floyd算法。若网络中的每条边都有一个数值，则找出两节点之间总权和最小的路径

Floyd算法算是最简单的算法，没有之一。其状态转移方程如下map[i , j] =min{ map[i , k] + map[k , j] , map[i , j] }；map[i , j]表示 i 到 j 的最短距离，K是穷举 i , j 的断点，ma

与传递闭包问题非常相似的一个问题是，能不能给出一个矩阵，根据矩阵可以以时间代价O的方式得到在一个有向代权图中任意指定端点之间的最短距离。求的这个矩阵的问题被称为每一对端点间的最小距离问题。和最小路径算法类似，这里用一个很大数字INFINITY来表示两个端点

和Dijkstra算法一样，弗洛伊德算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。以上图G4为例，来对弗洛伊德进行算法演示。以”邻接矩阵”为例对弗洛伊

和Dijkstra算法一样，弗洛伊德算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。假设图G中顶点个数为N，则需要对矩阵S进行N次更新。更新N次之后，操

和Dijkstra算法一样，弗洛伊德算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。假设图G中顶点个数为N，则需要对矩阵S进行N次更新。更新N次之后，操

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。请注意这些公路是单向的。这个问题这也被称为“多源最短路径”问题。2号城市无法到达4号城市，则设置e

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。核心算法1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。在G中包含有两点之间最短道

node_map = [[INF_val for val in xrange] for val in xrange]