Дейкстра на сетке

Нет смысла использовать приоритетную очередь, если я запускаю алгоритм 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

конец

Я собирался переписать его с приоритетной очередью, но просто не вижу в этом необходимости. Или я что-то упускаю?