设想你要从街道地图上的A点，通过可能的最短路径到达B点。举例来说，从洛杉矶的圣莫尼卡大道到好莱坞大道，如下图所示：
这种问题在生活中非常常见，我们（特别是生活在大城市的人们）会求助于苹果地图、谷歌地图、Waze等应用程序。当然，我们也有其他的考虑，如时间或路况，但根本的问题仍然是：从A到B的最短路径是什么？
我们可以用图来解决这个问题，相应的算法被称为最短路径。本节我们将介绍两种非常著名的算法，即Dijkstra算法和Floyd-Warshall算法。
9.5.1 Dijkstra算法
Dijkstra算法是一种计算从单个源到所有其他源的最短路径的贪心算法（你可以在第11章了解到更多关于贪心算法的内容），这意味着我们可以用它来计算从图的一个顶点到其余各顶点的最短路径。
考虑下图：
我们来看看如何找到顶点A和其余顶点之间的最短路径。但首先，我们需要声明表示上图的邻接矩阵，如下所示：
var graph = [[0, 2, 4, 0, 0, 0], [0, 0, 1, 4, 2, 0], [0, 0, 0, 0, 3, 0], [0, 0, 0, 0, 0, 2], [0, 0, 0, 3, 0, 2], [0, 0, 0, 0, 0, 0]]; 现在，通过下面的代码来看看Dijkstra算法是如何工作的：
this.dijkstra = function(src) { var dist = , visited = , length = this.graph.length; for (var i = 0; i < length; i++) { //{1} dist[i] = INF; visited[i] = false; } dist[src] = 0; //{2} for (var i = 0; i < length-1; i++) { //{3} var u = minDistance(dist, visited); //{4} visited[u] = true; //{5} for (var v = 0; v < length; v++) { if (!visited[v] && this.graph[u][v] != 0 && dist[u] != INF && dist[u] + this.graph[u][v] < dist[v]) { //{6} dist[v] = dist[u] + this.graph[u][v]; //{7} } } } return dist; //{8}}; 下面是对算法过程的描述。
行
{1}：首先，把所有的距离（dist）初始化为无限大（JavaScript最大的数INF = Number. MAX_SAFE_INTEGER），将visited初始化为false。行
{2}：然后，把源顶点到自己的距离设为0。行
{3}：接下来，要找出到其余顶点的最短路径。行
{4}：为此，我们需要从尚未处理的顶点中选出距离最近的顶点。行
{5}：把选出的顶点标为visited，以免重复计算。行
{6}：如果找到更短的路径，则更新最短路径的值（行{7}）。行
{8}：处理完所有顶点后，返回从源顶点（src）到图中其他顶点最短路径的结果。
要计算顶点间的minDistance，就要搜索dist数组中的最小值，返回它在数组中的索引：
var minDistance = function(dist, visited) { var min = INF, minIndex = -1; for (var v = 0; v < dist.length; v++) { if (visited[v] == false && dist[v] <= min) { min = dist[v]; minIndex = v; } } return minIndex;}; 对本节开始的图执行以上算法，会得到如下输出：
0 01 22 33 64 45 6 也可以修改算法，将最短路径的值和路径一同返回。
9.5.2 Floyd-Warshall算法
Floyd-Warshall算法是一种计算图中所有最短路径的动态规划算法（你可以在第11章了解到更多关于动态规划算法的内容）。通过该算法，我们可以找出从所有源到所有顶点的最短路径。
Floyd-Warshall算法实现如下：
this.floydWarshall = function { var dist = , length = this.graph.length, i, j, k; for (i = 0; i < length; i++) { //{1} dist[i] = ; for (j = 0; j < length; j++) { dist[i][j] = this.graph[i][j]; } } for (k = 0; k < length; k++) { //{2} for (i = 0; i < length; i++) { for (j = 0; j < length; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { //{3} dist[i][j] = dist[i][k] + dist[k][j]; //{4} } } } } return dist;}; 下面是对算法过程的描述。
行
{1}：首先，把dist数组初始化为每个顶点之间的权值，因为i到j可能的最短距离就是这些顶点间的权值。行
{2}：通过k，得到i途径顶点0至k，到达j的最短路径。行
{3}：判断i经过顶点k到达j的路径是否比已有的最短路径更短。行
{4}：如果是更短的路径，则更新最短路径的值。
行{3}是Floyd-Warshall算法的核心。对本节开始的图执行以上算法，会得到如下输出：
0 2 3 6 4 6INF 0 1 4 2 4INF INF 0 6 3 5INF INF INF 0 INF 2INF INF INF 3 0 2INF INF INF INF INF 0 其中，INF代表顶点i到j的最短路径不存在。
对图中每一个顶点执行Dijkstra算法，也可以得到相同的结果。