vlambda博客
学习文章列表

该算法由著名计算机科学家Edsger Wybe Dijkstra提出，使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题。该算法至今在各类地图等商业环境被广泛使用，是知名度非常高的算法之一。该算法的核心是贪心策略，以下图例子为展开

由于在竞赛中使用Dijkstra算法的普通算法（即上文讲述）经常会导致超时等问题，这里推荐一种Dijkstra算法的堆优化方法。

Dijkstra普通算法的实现需要从头到尾扫一遍点找出最小的点然后进行松弛。这个扫描操作就是坑害Dijkstra普通算法时间复杂度的罪魁祸首。所以我们使用小根堆，用优先队列来维护这个“最小的点”。从而大大减少Dijkstra算法的时间复杂度。

首先，我们需要往优先队列中push最短路长度，但是它一旦入队，就会被优先队列自动维护离开原来的位置，换言之，我们无法再把它与它原来的点对应上，也就是说没有办法形成点的编号到点权的映射。

我们用pair解决这个问题。

pair是C++自带的二元组。我们可以把它理解成一个有两个元素的结构体。更刺激的是，这个二元组有自带的排序方式：以第一关键字为关键字，再以第二关键字为关键字进行排序。所以，我们用二元组的first位存距离，second位存编号即可。

然后我们发现裸的优先队列其实是大根堆，我们如何让它变成小根堆呢？

有两种方法，第一种是把第一关键字取相反数，取出来的时候再取相反数。

弗洛伊德算法是由计算机科学家罗伯特·弗洛伊德提出的。是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

该算法首先列出从每一点出发找到可以直接通往其他顶点的初始化矩阵，我们以上图为例得到矩阵D：

我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4到3的路程d[4][3]原本是12。如果只通过1中转（4->1->3），路程将缩短为11（d[4][1]+d[1][3]=5+6=11）。其实1号到3号也可以通过2中转，使得1到3的路程缩短为5（d[1][2]+d[2][3]=2+3=5）。所以如果同时经过1和2中转的话，从4到3的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。

假如现在只允许经过1号顶点，求任意两点之间的最短路程，只需判断d[i][1]+d[1][j]是否比d[i][j]要小即可。d[i][j]表示的是从i号顶点到j号顶点之间的路程。d[i][1]+d[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1-n循环，j也是1-n循环。

通过以上方法，加入一部分暴力求解方法，即可求出第十二届蓝桥杯第一轮省赛C/C++的E题：