algorithm - first - Usando BFS para gráficos ponderados

shortest path bfs java

Question

Estaba revisando los algoritmos de ruta más corta de una sola fuente y en el video, el profesor menciona que BFS / DFS no se puede usar directamente para encontrar rutas más cortas en un gráfico ponderado (supongo que todo el mundo ya lo sabe) y me dijo que resolviera el motivo. tu propio.

Me preguntaba la razón / explicación exacta de por qué no se puede utilizar para gráficos ponderados. ¿Es debido a los pesos de los bordes o cualquier otra cosa? Alguien me puede explicar ya que me siento un poco confundido.

PD: Pasé por this pregunta y this pregunta.

Answer 1

Aunque esto es cierto, pero podría usar BFS/DFS en gráficos ponderados, con un pequeño cambio en el gráfico, si los pesos de su gráfico son enteros positivos, puede reemplazar un borde con peso n con n bordes con peso 1 con n-1 medio nodos Algo como esto:

A-(4)-B

estarán:

A-(1)-M1-(1)-M2-(1)-M3-(1)-B

Y no tenga en cuenta estos nodos intermedios (como M1, M2, M3) en sus resultados finales de BFS / DFS.

La complejidad de este algoritmo es O (V * M) y M es el peso máximo de nuestros bordes, si sabemos que en nuestras gráficas particulares M<log V este algoritmo podría considerarse, pero en general este algoritmo puede no ser tan bueno. actuación.

Answer 2

Considera una gráfica como esta:

A---(3)-----B
|           |
/-(1)-C--(1)/

La ruta más corta de A a B es a través de C (con un peso total de 2). Un BFS normal tomará el camino directamente de A a B, marcando B como se ve, y A a C, marcando C como se ve.

En la siguiente etapa, la propagación desde C, B ya está marcada como se ve, por lo que la ruta de C a B no se considerará como una ruta potencialmente más corta, y BFS le dirá que la ruta más corta de A a B tiene un peso de 3.

Puede usar el algoritmo de Dijkstra en lugar de BFS para encontrar la ruta más corta en un gráfico ponderado. Funcionalmente, el algoritmo es muy similar a BFS y se puede escribir de forma similar a BFS. Lo único que cambia es el orden en que se consideran los nodos.

Por ejemplo, en el gráfico anterior, comenzando en A, un BFS procesará A -> B, luego A -> C, y se detendrá allí porque se han visto todos los nodos.

Por otro lado, el algoritmo de Dijkstra operará de la siguiente manera:

1. Considere A -> C (ya que este es el peso del borde más bajo de A)
2. Considere C -> B (ya que este es el límite de menor peso de cualquier nodo al que hemos llegado hasta ahora, que aún no hemos considerado)
3. Considere e ignore A -> B ya que B ya se ha visto.

Tenga en cuenta que la diferencia radica simplemente en el orden en que se inspeccionan los bordes. Un BFS considerará todos los bordes de un solo nodo antes de pasar a otros nodos, mientras que el algoritmo de Dijkstra siempre considerará el borde invisible de menor peso, desde el conjunto de bordes conectados a todos los nodos que se han visto hasta ahora . Suena confuso, pero el pseudocódigo es muy simple:

create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
   vertex v = top of heap
   pop top of heap
   for each vertex u connected to v:
       if dist[u] > dist[v] + weight of v-->u:
           dist[u] = dist[v] + weight of edge v-->u
           place u on the heap with weight dist[u]

Este GIF de Wikipedia proporciona una buena visualización de lo que sucede:

Tenga en cuenta que esto parece muy similar al código BFS, la única diferencia real es el uso de un montón, ordenado por distancia al nodo, en lugar de una estructura de datos de cola regular .