上一篇博客论述了图的最短路径问题。 我该怎么寻找两个顶点之间的最短路径？ 其实，这个问题不应该称为“最短”路径问题，而应该称为“最低价”路径问题。 之所以这么说，是因为我们赋予图中的边缘权利(weight )，也称为权重，相当于通过边缘的“代价”，一般是正的。 例如下图(边旁边的数字是该边的权重) ) ) ) )。
简单地考虑一个路径上边的条数，从v0到v6的最短路径应该是v0-v3-v6。 但是，考虑到边缘权重，从v0到v6的“最便宜”路径是v0-v1-v4-v6，其总权重是3 (路径内所有边缘的权重之和)，如果进行v0-v3-v6的路径，则总权重为
边上加权的图称为权利贴图，相反，边上加权的图称为权利贴图。 显然，与授权贴图相比，授权贴图在许多情况下更适用。 例如，用赋权地图表示城市道路时，权重越大道路状况越差，权重越大通行费越高。
实际上，不考虑权重的最短路径问题是所有边的权重为1的“最便宜”路径问题，例如从上图的所有边中除去权重后的无权图也可以这样表示：
为了方便，“最便宜”的路径称为最短路径。
接下来，让我们从没有简单权限的情况开始，看看如何找到两个顶点之间的最短路径。 但是到了这一步，有必要说明一件有趣的事情。 那就是，查找从x到y的最短路径比查找从x到所有顶点的最短路径慢(你无权查找所有顶点)。
我们可以很容易地分析发生这种情况的原因。 寻找从x到y最短路径的最直接的方法是让程序从x出发，不断走，直到沿着可行的边走到y。 但是去y的时候，谁也不能保证刚才走的路是最短的。 也就是说，除非你绕过了图中的顶点，否则必须绕过所有顶点才能确保去y后的路径最短。 而且，在这个过程中你一定是，所以要想找到从x到y的最短路径，就必须找到从x到所有顶点的最短路径。
当然，也存在专门寻找点到点最短路径的想法，但目前单独寻找从x到y的最短路径并不比寻找从x到所有顶点的最短路径快，所以接下来要研究的问题其实是单源的最短路径问题即，给出起点(源)，求出与所有顶点的最短路径。 如果有通往所有顶点的最短路径，我们也自然有通往顶点y的最短路径。
不带图寻找单源最短路径的想法是我们上述的“最直接的做法”。 为便于说明，假设边(a，b )存在时，b是a的“指示”顶点。 那么，对无权图进行单一源的最短路径搜索就是这样的：
首先，将起点路径长度设为0，将其他顶点的路径长度设为负数(表示，下面的例子以v1为起点)
接下来，如果将起点所指顶点的路径长度设为1，则可以肯定的是，只有路径长度为0的起点所指的顶点的路径长度为1，在本例中为v3和v4 :
接着，若将路径长度1的顶点(v3和v4 )所指定的顶点的路径长度设为2，则同样能够确认只有路径长度1的顶点所指定的顶点的路径长度为2。 但是，此时出现了问题。 v3是v4指向的顶点，但v3的路径长度显然不应该设置为2。 因此，必须将已知路径长度的顶点标记为“已知”。 已知顶点不更改路径长度。 具体方法在给出代码时注明。 在本例中，路径长度设置为2的顶点是v2、v5和v6。
然后，继续这样的步骤，将路径长度为2的顶点所指的顶点的路径长度设为3。 但是，在本例中，路径长度为2的顶点所指的顶点没有未知的顶点，因此算法结束。
虽然上述步骤随着图的规模的增大而变多，但是很容易看出，将路径长度I的顶点所指的未知顶点的路径长度设为i 1，I从0开始，将当前的路径长度I的顶点没有指向其他顶点或者所指的顶点全部已知作为结束条件。
需要注意的是结束条件的说法，并不是所有顶点都要求成为已知。 因为，在确定某个顶点是起点之后，某个顶点可能无法从起点出发而到达。 例如，在我们示例中的v0中，不存在从v1到v0的路径。
接下来要做的就是用代码实现我们说的想法。 此时，需要注意的是，我们不想直接插手图中。 因为图中可能还有其他使用，直接插手图也不方便。 因为图中的顶点可能没有用于指示是否已知的域，也可能没有用于指示从起点到自己的最短路径长度的域。
因此，我们的方法是将最短路径的计算结果保存在线性表中，其结构如下
其中“一行”是线性表中的一个元素，每行的四个单元格是一个元素中的四个字段。 顶点、是否已知、与起点的最短路径长度、最短路径中自身前面的顶点。
那么，首先计算最短路径的过程用本表表示，如下所示。
要知道从起点到顶点的y的最短路径，只需找到y顶点并查看其距离域即可。 另外，想知道整个路径是如何进行的时，只要将y的preV追溯到起点就可以知道。 以下是从输出起点到给定终点的最短路径的示例。
//路径表的要素定义假设为顶点vx即数字x，所以要素没有v
ertex域structpathNode
{
boolknown;
intdistance;
size_t preV;
}
//路径表
structpathNode pathTable[numVertex];
void printPath(size_t end,struct node*pathTable)
{
size_t preV=pathTable[end].preV;if(pathTable[preV].distance!=0)
printPath(preV,pathTable);elseprintf("%d",preV);
printf("->");
printf("%d",end);
}
下面是上述无权最短路径思路的一个简单伪代码实现：
//无权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)
{
pathTable[start].known=true;
pathTable[start].distance=0; //若pathTable[x].distance为0，则其preV是无用的，我们不予理睬//初始化pathTable中的其他元素//curDis即当前距离，我们要做的是令distance==curDis的顶点所指的未知顶点的distance=curDis+1
for(int curDis=0;curDis
{for(int i=0;i
{if(!pathTable[i].known&&pathTable[i].distance==curDis)
{
pathTable[i].known=true;//遍历pathTable[i]所指向的顶点X
{if(!pathTable[X].known)
{
pathTable[X].preV=i;
pathTable[X].distance=curDis+1;
}
}
}
}
}
}
与上一篇博文的拓扑排序一样，上面的最短路径算法还有改进空间。当我们寻找符合distance==curDis条件的顶点时，我们用的是直接遍历数组的方法，这使得我们的算法时间复杂度达到了O(nv2)(nv为顶点个数)，所以我们要改进的就是“寻找符合条件的顶点”的过程。我们可以创建一个队列来存储“需要处理的顶点”，该队列初始时只有起点，当我们修改了某个未知顶点的distance后，我们就将该顶点入队，而当我们令curDis递增后再次寻找distance==curDis的顶点时，我们只需要令队列元素出队即可获取到想要的顶点。这个过程口述难以表达清楚，下面是应该足够清晰了的伪代码：
//无权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)
{//初始化pathTable//创建队列pendingQueue//将起点start入队
size_t curVertex;while(!empty(pendingQueue))
{
curVertex=Dequeue(pendingQueue);
pathTable[curVertex].known=true;//遍历curVertex指向的顶点X
{if(!pathTable[X].known)
{
pathTable[X].distance=pathTable[curVertex].distance+1;
pathTable[X].preV=curVertex;
Enqueue(X,pendingQueue);
}
}
}
}
这样一来，我们就将无权最短路径算法的时间复杂度由O(nv2)降低到了O(nv+ne)(ne即边的条数)。此外，上述算法对于无向有圈图也是一样生效的，原因就不赘述了，道理是简单的。
接下来的问题是如何对有权图进行单源最短路径的寻找。有权图的最短路径显然比无权图要难找，原因在于我们不能套用无权算法的思路，直接令已知顶点所指未知顶点的distance=curDis+weight(weight即两顶点间路径的权重，此处简写)，以下图为例：
若我们令v0作为起点，然后令v0所指的未知顶点的distance=v0.distance+weight，那么v3的distance就会变成5，可是实际上v3的distance应改为2。
解决的思路是：我们罗列出所有已知顶点指向的所有未知顶点，看这些未知顶点中谁的distance被修改后会是最小的，最小的那个我们就修改其distance，并认为它已知。
以上图为例，我们一步步走一遍来加深一下理解：
首先是正常的初始化(我们将边的权重也标识出来)，假设起点为v0：
接着我们罗列出所有已知顶点(只有v0)指向的所有未知顶点：v1、v2、v3。然后发现若修改它们的distance，则v1.distance=v0.distance+1=1，v2.distance=v0.distance+3=3，v3.distance=v0.distance+5=5。显然v1被修改后的distance是未知顶点中最小的，所以我们只修改v1的distance，并将v1设为已知，v2、v3不动：
接着我们继续罗列出所有已知顶点(v0、v1)指向的所有未知顶点：v2、v3、v4。然后发现若修改它们的distance，则v2.distance=v0.distance+3=3，v4.distance=v1.distance+1=2，v3.distance=v1.distance+1=2(虽然v0也指向v3，但是通过v0到v3的路径长大于从v1到v3，所以v3的distance取其小者)，其中v3和v4的新distance并列最小，我们任选其一比如v4，然后只修改v4的distance，并将v4设为已知，其它不动：
继续，我们罗列出所有已知顶点(v0、v1、v4)指向的所有未知顶点：v2、v3、v6，发现若修改，则v2.distance=3，v3.distance=2，v6.distance=3，所以我们只修改v3的distance，并将v3设为已知：
继续，我们罗列出所有已知顶点(v0、v1、v3、v4)指向的所有未知顶点：v2、v5、v6，发现若修改，则v2.distance=3，v5.distance=10，v6.distance=3，我们在v2和v6中任选一个如v2，只修改v2.distance，并将v2设为已知：
继续，我们罗列出所有已知顶点指向的所有未知顶点：v5、v6，发现若修改，则v5.distance=5，v6.distance=3，所以我们只修改v6：
最后，罗列出的未知顶点只有v5，若修改，其distance=5，我们将其修改并设为已知，算法结束：
其实上述算法的核心部分就是：
1.找到所有已知顶点
2.将所有已知顶点指向的所有未知顶点罗列出来
3.计算这些未知顶点的最小distance，然后再确定其中新distance最小的顶点X
4.只修改X的distance，并将X设为已知
5.回到第二步，若所有已知顶点都没有指向未知顶点，则结束
而这个算法就是Dijkstra算法的雏形。
Dijkstra算法核心部分简化的说法就是：找到所有可确定distance的未知顶点中新distance最小的那个，修改它并将它设为已知。
用伪代码描述就是这样：
//有权最短路径计算，图存于邻接表graph，结果存入pathTable，起点即start
void weightedPath(Node* graph,struct pathNode*pathTable,size_t start)
{//初始化pathNode数组
size_t curV;while(true)
{//找到可确定distance的未知顶点中新distance最小的那个，存入curV，若没有则跳出循环//令pathNode[curV].distance和pathNode[curV].prev修改为正确的值
pathNode[curV].known=true;
}
}
可以确定的是，Dijkstra算法也可以应用于无权图，只要给无权图中的每条边加个值为1的权重即可。并且如果你将无权算法与Dijkstra算法进行对比，就会发现那个无权算法其实就是Dijkstra算法的“特例”，在无权算法中，我们之所以不需要去找“distance最小的未知顶点”，是因为我们可以肯定已知顶点所指向的未知顶点就是“distance最小的未知顶点”。
不用想都知道，Dijkstra算法中的循环中的两行伪代码其实意味着大量的操作：找到可以确定distance的未知顶点，计算它们的distance，比较出最小的那个，修改……
显然，Dijkstra算法的核心部分是可以改进的，改进的思路与无权算法也很相像，即“加快寻找符合条件的顶点的过程”。其中一种改进方式是计算出未知顶点的新distance后，将{未知顶点，新distance}对插入到以distance为关键字的优先队列中，而不是直接抛弃非最小distance的那些未知顶点(这是一个很大的浪费)。这样在下一次寻找“distance最小的未知顶点”时，我们可以通过优先队列的出队来获得，从而避免了遍历整个数组来寻找目标的情况。这个想法要细化实现的话，还有不少坑要避开，不过我写到这儿时深感表达之困难与疲惫，所以这篇博文就此打住，如果博文中有什么不对之处，可以在评论区指出，谢谢~
附：如果有权图中存在权重为负值的情况，则计算单源最短路径将会更加困难，不过可以确定的是，如果有权图中存在圈与负权边，且负权边在圈中，使得圈的路径长为负，那么单源最短路径的计算是无法进行的，因为你可以在这个圈中永远走下去来使路径长不断“减小”。解决有负值权重边的图的最短路径算法是在Dijkstra的算法上进行改进得来的，本文不予讲解(或许以后会有一篇文章介绍)，有兴趣的可以自行搜索。