O algoritmo de Dijkstra é apenas BFS com uma fila de prioridade?

De acordo com esta página , o algoritmo de Dijkstra é apenas BFS com uma fila de prioridade. É realmente assim tão simples? Eu acho que não.

Você pode implementar o algoritmo de Dijkstra como BFS com uma fila de prioridade (embora não seja a única implementação).

O algoritmo de Dijkstra se baseia na propriedade de que o caminho mais curto de a também é o caminho mais curto para qualquer um dos vértices ao longo do caminho. É exatamente isso que o BFS faz.$s$$t$

Ou em outra perspectiva: como o algoritmo de Dijkstra se comportaria se todos os pesos fossem 1? Exatamente como o BFS.

Primeiro, como podemos adaptar o BFS ao gráfico ponderado mais geral ?$G = (V, E)$

Aqui está uma idéia do livro "Algoritmos (Seção 4.4)", de Dasgupta et al:

$e = (u,v)$$E$$l_e$$l_e$$1$$l_e - 1$$u$$v$

$G'$$G$$G'$

$G$$G'$

$G'$$l_e$

Terceiro, como o algoritmo Dijkstra se comporta em gráficos não ponderados?

Ele se comporta exatamente da mesma forma que o BFS. Nós elaboramos isso a partir de dois pontos principais.

• Em "relaxamento".

  Para o algoritmo Dijkstra no gráfico geral ponderado, o relaxamento é

  for all edges (u,v) in E:
      if dist(v) > dist(u) + w(u,v)
         dist(v) = dist(u) + w(u,v)
  

  $dist(v) = \infty$$w(u,v) = 1$

  for all edges (u,v) in E:
      if dist(v) = \infty
         dist(v) = dist(u) + 1
  

• Em "fila de prioridade".

  Quando o algoritmo Dijkstra é executado em gráfico não ponderado, a qualquer momento, a fila de prioridade contém no máximo dois valores distintos (distância). Portanto, uma fila FIFO de BFS é suficiente.