1

如果我在“网格”上运行 dijskstra 的算法，那么使用优先级队列是没有意义的，对吧？

网格将是这样的地图： 顶点：

 ___________________
|A|_|_|_|_|_|_|_|_|_|
|C|B|_|_|_|_|E|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|D|_|_|_|_|_|F|_|_|_|
|_|_|_|_|_|_|_|_|_|_|

边缘：

A <-> C
C <-> B
C <-> D
D <-> F
B <-> E
E <-> F

换句话说，每条边都连接到与其水平或垂直的顶点但不能对角连接的地图（例如，不允许从 A 到 B 或 A 到 F 的边）。

此外，边缘的权重对于它们在网格中的位置是直观的。例如，A <-> C 的边权重为 1，C <-> B 为 1，C <-> D 为 6，B <-> E 为 5，D <->F 和 E <-> F 为两者都 6。

不久前我为这样的图实现了 dijsktra 的算法，现在我需要对其进行优化，使其尽可能快。我当前的实现（红宝石）：

def self.dj_start(g,source, goal)
    t = Time.now
    visited, distances, paths, already_queued = {}, {}, {}, {}

    curr = g.verticies[source]
    queue = [] # 

    queue.push(curr)
    already_queued[curr] = true
    distances[curr] = 0
    paths[curr] = curr
    @count = 0
    while(!queue.empty?)
      run_dijkstra(g, visited, distances, paths, queue, already_queued, goal)
    end
    t = Time.now - t
    print "ran dijkstra in #{t}s count = #{@count}\n"
    return [paths, distances]
end

def self.run_dijkstra(g, visited, distances, paths, queue, already_queued, goal)
curr = g.verticies[queue.delete_at(0)]
visited[curr] = true

curr.edges.each do |e|
    @count+=1
      if !already_queued[e.vertex] && !visited[e.vertex]
        queue.push(e.vertex) 
        already_queued[e.vertex] = true
      end

      nd = e.weight+distances[curr]
      if distances[e.vertex].nil? || nd < distances[e.vertex]
        distances[e.vertex] = nd
        paths[e.vertex] = curr

        if e.vertex.eql?(goal) # minor optimization
          queue = []
          return 1 # Code for exit due to this very minor optimization
        end
      end # end distance check
end

结尾

我打算用优先级队列重写它，但我只是不认为这样做有必要。还是我错过了什么？

4

1 回答 1

0

通常使用广度优先搜索来解决类似的问题，其中每个单元格都是图中的一个顶点。仍然在您解决的问题中，与网格中的单元格数量相比，有效位置的数量非常低，所以也许您的方法可以工作。请注意，边缘权重（即您需要在两个位置之间移动的最小单元数）应该以某种方式提供给您的程序。如果不是这种情况，您将不得不使用 BFS 计算这些，因此 Dijkstra 没有意义。

说了这么多，我来回答你的问题。如果以您在此处显示的方式提供边缘，则有理由使用优先级队列。它将算法的计算复杂度降低一个数量级。对于较大的网格，这将是显而易见的。

顺便说一句，ruby 有一个非常酷的 gem，它实现了斐波那契堆。尽管将斐波那契堆用于您在此处显示的大小的 grpah 可能会有点矫枉过正，但我​​一直认为拥有基于斐波那契堆的 dijkstra 会很酷。

希望这个答案有帮助。

于 2012-12-20T20:52:06.750 回答