algorithm - 网格上的迪杰斯特拉

Question

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

网格就是这样的 map :顶点:

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

边缘:

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

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

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

我不久前为这样的图实现了 dijsktra 的算法，现在我需要优化它以使其尽可能快。我当前的实现( ruby ):

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

结束

我打算用优先级队列重写它，但我认为没有这样做的必要。还是我遗漏了什么？

Answer 1

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

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

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

希望这个回答对您有所帮助。