Dijkstra 的最短距离

• 下载源代码 - 21 KB 

介绍 

下面的文章演示了一个 .NET 实现的 Dijkstra 算法，用于在一个连通的无向图中查找两个节点之间的最小距离路径。为此，使用的技术是 .NET 4.0、Visual Studio 10 和 WPF 用于图形用户界面。

背景

每个图的基本元素是节点和边。一般来说，图是一种可以表示任何事物的抽象。最容易理解它的方式（特别是对于本文）是将其视为一张地图，其中节点是城市，边是连接的道路。然而，图也可以用来表示其他事物。

基本元素

在这个特定的例子中，单个节点具有几个重要属性——一个区分它与其他节点的标签，一组连接它的边，一个指示节点是否已被访问的属性，用于其图形表示的坐标，以及总成本。稍后我们将详细讨论总成本的概念。它是比较的基础，将帮助我们确定下一步选择哪个节点。

边是图中两个节点之间的连接。有两种边——有向边和无向边。有向边可以看作是单向街道。它表明虽然存在从节点 A 到节点 B 的路径，但反方向（从 B 到 A）是不可能的。为了做到这一点，我们需要另一条连接 A 和 B 的边，其方向指向 A。另一方面，无向边不施加此类限制，并允许我们双向通行。对于边重要的属性是连接它的结束节点，边是否已被访问，它的权重以及方向（如果有的话）。 

通常，一个图只有一种类型的边。根据图的边类型，它被认为是定向的或无向的。在本例中，我们将考察无向图。这两个元素在示例中有相应的实现：`Node` 类和 `Edge` 类。此外，还有两个数据结构有助于我们同时提高算法的清晰度和速度：`ReachableNode` 类和 `ReachableNodeList` 类。这两个辅助类将使我们能够根据其总成本快速对未访问的节点进行排序，并以最高效的方式选择最佳节点。

算法

Dijkstra 算法用于查找图中两个节点之间的最短路径，通常被描述为“贪心”算法。也就是说，在每一步，算法都会选择总成本最低且尚未访问的节点。

让我们以下面的简单示例为例，并尝试手动运行算法，看看每一步需要做什么。假设我们要从节点 1 到节点 8。我们首先考虑起始节点的所有邻居（或在代码示例中称为可达节点）——节点 2、4 和 5。从 1 到 2 的成本是 21，从 1 到 5 的成本是 13，从 1 到 4 的成本是 27。我们的最佳选择是转到节点 5。此时，我们注意到我们已经访问了节点 1 和 5 以及连接它们的边。更重要的是，我们注意到我们是通过连接节点 1 和 5 的边到达节点 5 的。

现在我们在节点 5。由于节点 5 不是期望的目的地，我们将再次运行算法迭代。我们从当前位置发现所有额外的可达节点——节点 3 和 6。我们排除节点 1，因为它已经被访问过（这实际上是我们开始的地方）。到目前为止的总成本是 13。

节点 2 和 4 的成本相等，因为在这两种情况下总成本将是 13 + 18 = 31。对于节点 6，总成本将是 35，对于节点 3 则是 49。即使这些选项目前不是最佳选项，我们也会将它们放在一边，因为如果我们用完了其他选择，它们可能会变得有吸引力。由于去节点 2 和去节点 4 的成本相同，让我们考虑这种情况。当我们到达节点 2 时，总成本是 31，并且由于我们已经访问了节点 1 和 5，我们只能去节点 6。这将产生总成本 31 + 51 = 82。这不是最佳选择，因为我们可以从节点 5 到 4，总成本将是 31。我们将节点 2 和边 5-2 标记为已访问，并记下我们是从节点 5 到达节点 2 的。现在我们在节点 4，总成本是 31。从这里，我们可以去节点 3 和 7，分别产生总成本 40 和 49。我们有一个更好的选择——从 5 到 6，总成本为 13 + 22 = 35。一如既往，我们将节点 6 标记为已访问，并记住我们是通过来自节点 5 的边访问它的。

在我们剩余的选项中，有两个是等价的。我们可以从 4 到 3，从 6 到 8，总成本为 40。假设我们首先考虑第一个选项。我们将节点 3 标记为已访问，并记下我们是从节点 4 到达那里的。此时，唯一未访问的节点是 7 和 8。我们有的选择是：从 4 到 7，3 到 7，3 到 8，以及 6 到 8，总成本分别为 49、48、50 和 40。我们的最佳选择是从 6 到 8，我们到达了最终目的地。此时，我们完成了任务。剩下的工作是突出最佳路径。这相对容易做到，因为在每一步我们都记下了访问该节点的边。因此，我们所需要做的就是沿着它向后追踪。我们从节点 8 开始，并且是从节点 6 到达它的。我们从节点 5 到达节点 6，我们从节点 1 到达节点 5。因此，从 1 到 8 的最小距离路径是 1-5-6-8，总成本为 40。

使用应用程序

为了使用该应用程序，用户首先需要创建节点以及它们之间的边。要创建一个节点，用户需要在画布上单击。要连接两个节点，用户需要依次选择在画布上创建的两个节点。同样，要查找两个节点之间的最小距离，用户需要单击“查找最小距离”按钮并在画布上选择两个节点。“清除”按钮允许用户清除画布并构建新图。“重置”允许用户在找到最小距离之前回到图的初始状态。