2.7　用迪杰斯特拉算法找到最短路径

迪杰斯特拉算法最初的设计目标是解决图的单源最短路径问题。所以，这个算法找到的是从单一起点到各个终点的最低成本的路线。我们将学习如何用两种不同的方式使用这个算法。

准备工作

考虑到.NET框架和Mono都没有预定义操作二叉堆或优先队列的结构，第一件要做的事是从游戏编程百科网站（GPWWiki）把二叉堆类导入到项目中。

操作步骤

我们要学习如何使用与其他算法相同个数的参数实现迪杰斯特拉算法，然后解释如何修改算法，以便最大限度地发挥它的初衷：

1. 定义GetPathDijkstra函数及其内部变量：

2. 将源节点添加到堆中（像优先队列那样），然后赋一个无限大的距离值给所有除源节点之外的节点：

3. 定义一个循环以遍历非空队列：

4. 编写到达终点时的代码：

5. 另外，把访问过的节点和邻接点添加到队列中，然后返回路径（如果存在一条从源点到终点的路径，值就不为空）：

运行原理

迪杰斯特拉算法与BFS算法的原理相似，但是要考虑非负边的成本，以便构建出从源点到每个终点的最佳路线，这就是用数组存储前向顶点的原因。

延伸阅读

我们还要学习如何修改现有的迪杰斯特拉算法，以便用预处理的技术解决问题并优化路径查找时间。这可以看作是三大步：修改主算法，创建预处理函数（可以用编辑器模式），最后定义路径获取函数。

1. 修改主函数的签名：

2. 改变返回值：

3. 移除“操作步骤”第4步中的代码：

另外，删除开头处下面这行代码：

4. 在Graph类中创建一个新的成员值：

5. 定义预处理函数DijkstraProcessing：

6. 实现新的GetPathDijkstra函数，用于获取路径：

你可能没有注意到，我们没有实现BuildPath方法，这是因为在2.5节已经讨论过。