Dijkstra 最短路径算法的快速优先队列实现

• 下载 FastDijkstra-noexe.zip - 41.1 KB
• 下载源代码 - 57.8 KB

引言

由于我主要从事图像处理和计算机视觉方面的工作，我会在文章中分享一些在信号处理、问题解决等方面可能遇到的解决方案。图像分割任务通常需要大量的计算。在这种情况下，图像通常被解释为像素图或图。其中一个问题可能是在给定的无向加权图中寻找最短路径。

起初，我并没有打算实现这个算法。然后，我意识到网上没有人为 C# 实现一个适合我需求的、高效的 Dijkstra 算法。特别是对于有向加权图，很难找到一个现成的解决方案。

背景

要理解本文并正确使用代码，你需要了解 Dijkstra 算法的作用以及堆（优先队列）是什么。让我们先从 Dijkstra 算法开始。

Dijkstra 算法

给定图中的一个源 顶点（节点），该算法找到该顶点与所有其他顶点之间成本最低（即最短）的路径。它也可以用于查找从单个顶点到单个目标顶点的最短路径成本，一旦确定了到目标顶点的最短路径，就可以停止算法。例如，如果图的顶点代表城市，边路径成本代表连接的城市对之间的驾驶距离，则 Dijkstra 算法可用于查找一个城市与所有其他城市之间的最短路线。

该算法由 Edsger Dijkstra 于 1959 年发明，至今仍是解决最短路径算法的最佳方案之一。

这是一个简单的伪代码（不同实现可能有所不同）

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations

 3          dist[v] := infinity               // Unknown distance
                                              // function from source to v
 4          previous[v] := undefined
 5      dist[source] := 0                     // Distance from source to source

 6      Q := copy(Graph)                      // All nodes in the graph
                                              // are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop

 8          u := extract_min(Q)               // Remove and return best vertex
                                              // from nodes in two given nodes
                                              // we would use a path finding algorithm
                                              // on the new graph,
                                              // such as depth-first search.

 9          for each neighbor v of u:         // where v has not yet been removed from Q.
10              alt = dist[u] + length(u, v)

11              if alt < dist[v]              // Relax (u,v)
12                  dist[v] := alt

13                  previous[v] := u
14      return previous[]

可以看出，previous[] 数组包含从一个点到另一个点的路径。这里的瓶颈在于 extract_min 函数。给定一个数组，此函数返回最小值。Dijkstra 算法的朴素实现（网上大部分都能找到）使用线性数组搜索来计算这个最小值。然而，这种方法性能非常差。这时，优先队列就派上用场了。

优先级队列

优先队列（堆）是非常精巧的数据结构，允许

• 将一个带有优先级值的元素添加到队列中
• 从队列中移除具有最高优先级的元素并返回它
• （可选）查看具有最高优先级的元素而不移除它

实现优先队列数据类型的一种简单方法是维护一个元素列表，并在每次进行“最小”或“查看”操作时搜索该列表以找到优先级最高的元素。此实现的插入元素操作需要 O(1) 时间，而“最小”或“查看”操作需要 O(n) 时间。有许多更高效的实现可用。Emde Boas 实现是最快的实现之一，其每个操作的时间复杂度为 O(log(log(n)))。

在我的实现中，我使用了 BenDi 的代码，它相当直观。我还通过减少通用性和使用 List 结构而不是 ArrayList 来修改它，以降低复杂度和开销。代码可以在 这里 找到。

结果算法

我使用的是上述伪代码的一个简单的修改版本。下面是伪代码的概述

Take the origin vertex, set the weight of the shortest path to 0 and
push it onto the priority queue.

while the priority queue is not empty, pop an entry <v,w_v,p_v>where
v is the vertex, w_v and p_v are the augmented labels of v.
foreach edge e=(v,u) in G, where u has augmented labels w_u, p_u.

if wt(e) + w_v < w_u then
set p_u to v
set w_u to wt(e) + w_v
add <u,>to the priority queue.

Using the Code

Dijkstra 类非常易于定制。其思想是假设一个虚拟图（假设的）。图由一组节点组成，并为每个节点分配权重。非常可能将权重表示为旅行距离，将节点表示为顶点。因此，我们有两个数组，一个二维数组和一个一维数组。在这种情况下，你应该能够提供每个节点的权重以及邻居列表（连接到给定节点的节点列表）。你可以预先计算这些值，也可以在运行时提供这些值。预先计算将带来更快的运行时性能，但需要更多的内存和带宽。要使用代码

public delegate float InternodeTraversalCost(int start, int finish);

此委托是指向一个函数，该函数返回给定起始节点和结束节点的成本值。你必须提供此函数。在我的例子中，它是一张图像，所以我是通过用像素的成本及其连接节点的成本填充二维数组来计算的。

public delegate IEnumerable<int> NearbyNodesHint(int startingNode);

此委托是指向一个函数，该函数根据输入节点返回节点列表。节点列表就是给定节点的邻居（连接到该节点的节点）。最后，实例化如下

dijkstra = new DijkstraFast(totalNodes, 
  new DijkstraFast.InternodeTraversalCost(getInternodeTraversalCost), 
  new DijkstraFast.NearbyNodesHint(GetNearbyNodes));

生成的代码如下所示

// A struct containing both the minimum distance and minimum path 
// to every node from the given <paramref name="start"/> node. 

public virtual Results Perform(int start)
{

    // Initialize the distance to every node from the starting node. 
    float[] d = GetStartingTraversalCost(start);

    // Initialize best path to every node as from the starting node. 
    int[] p = GetStartingBestPath(start);

    BasicHeap Q = new BasicHeap();

    for (int i = 0; i != TotalNodeCount; i++)
        Q.Push(i, d[i]);

    while (Q.Count != 0)
    {
        int v = Q.Pop();
        foreach (int w in Hint(v))
        {
            if (w < 0 || w > Q.Count - 1) continue;
            float cost = TraversalCost(v, w);
            if (cost < float.MaxValue && d[v] + cost < d[w])
            // don't let wrap-around negatives slip by 
            {
                // We have found a better way to get at relative 
                d[w] = d[v] + cost; // record new distance 
                p[w] = v;
                Q.Push(w, d[w]);
            }
        }
    }
    return new Results(p, d);
}

上述算法使用了我创建的基本自定义堆。如果你想更通用，我还将提供一个使用 BenDi 代码的实现

// start: The node to use as a starting location. 
// A struct containing both the minimum distance and minimum path 
// to every node from the given <paramref name="start"/> node. 

public virtual Results Perform2(int start)
{

    // Initialize the distance to every node from the starting node. 
    float[] d = GetStartingTraversalCost(start);

    // Initialize best path to every node as from the starting node. 
    int[] p = GetStartingBestPath(start);

    BinaryPriorityQueue Q = new BinaryPriorityQueue();

    for (int i = 0; i != TotalNodeCount; i++)
        Q.Push(new QueueElement(i,d[i]));

    while (Q.Count!=0)
    {

        int v = ((QueueElement)Q.Pop()).index;

        foreach (int w in Hint(v))
        {
            if (w <0 || w > Q.Count-1) continue;
            float cost = TraversalCost(v, w);
    
            if (cost < float.MaxValue && d[v] + cost < d[w])
            // don't let wrap-around negatives slip by 
            {
                // We have found a better way to get at relative 
                d[w] = d[v] + cost; // record new distance 
                p[w] = v;
                Q.Push(new QueueElement(w, d[w]));
            }
        }
    }

    return new Results(p, d);
}

关注点和结论

该算法易于使用和升级。我将继续寻找使用更优堆的实现。

祝你编码愉快...

历史

开始...