Una lista de adyacencia
Este grafo tiene cinco vértices. En Java se guarda como una lista de adyacencia. Un Map asocia cada vértice con la lista de sus vecinos. No es dirigido: cada arista se agrega en los dos sentidos.
Este grafo tiene cinco vértices. En Java se guarda como una lista de adyacencia.
Un Map asocia cada vértice con la lista de sus vecinos.
No es dirigido: cada arista se agrega en los dos sentidos.
Este grafo tiene cinco vértices. En Java se guarda como una lista de adyacencia. Un Map asocia cada vértice con la lista de sus vecinos. No es dirigido: cada arista se agrega en los dos sentidos.
BFS usa dos estructuras: un Set de visitados y una cola de pendientes.
A se marca como visitado al encolar, no al desencolar.
BFS usa dos estructuras: un Set de visitados y una cola de pendientes. A se marca como visitado al encolar, no al desencolar.
La cola entrega a A, el primero que entró, y se agrega al orden de visita.
Sus vecinos B y C se marcan y entran a la cola: son la capa 1.
La cola entrega a A, el primero que entró, y se agrega al orden de visita. Sus vecinos B y C se marcan y entran a la cola: son la capa 1.
Sale B y encola a D. Al salir C, D ya está visitado: no entra dos veces.
Luego D encola a E. BFS explora por capas: 1 salto, 2 saltos, 3 saltos.
Por eso BFS encuentra el camino con menos aristas.
Sale B y encola a D. Al salir C, D ya está visitado: no entra dos veces. Luego D encola a E. BFS explora por capas: 1 salto, 2 saltos, 3 saltos. Por eso BFS encuentra el camino con menos aristas.
Ahora cada arista tiene un peso: kilómetros, minutos o costo.
Para BFS, el camino de A a B es la arista directa: 1 salto, pero cuesta 4.
Por A → C → B hay más saltos, pero cuesta 2 + 1 = 3. Menos aristas no es lo más barato.
Ahora cada arista tiene un peso: kilómetros, minutos o costo. Para BFS, el camino de A a B es la arista directa: 1 salto, pero cuesta 4. Por A → C → B hay más saltos, pero cuesta 2 + 1 = 3. Menos aristas no es lo más barato.
Dijkstra usa una cola de prioridad: siempre sale el vértice pendiente más barato.
Desde A, B queda a 4 y C a 2. Sale C, que es el más barato.
Relajar: por C, B cuesta 2 + 1 = 3, menos que 4. Su distancia se actualiza.
Dijkstra usa una cola de prioridad: siempre sale el vértice pendiente más barato. Desde A, B queda a 4 y C a 2. Sale C, que es el más barato. Relajar: por C, B cuesta 2 + 1 = 3, menos que 4. Su distancia se actualiza.
Sale B con 3: por B, D cuesta 3 + 5 = 8, mejor que 10. Se relaja otra vez.
Sale D con 8 y E queda a 8 + 3 = 11. Cada vértice procesado ya es definitivo.
Sale B con 3: por B, D cuesta 3 + 5 = 8, mejor que 10. Se relaja otra vez. Sale D con 8 y E queda a 8 + 3 = 11. Cada vértice procesado ya es definitivo.
El resultado es el camino más corto desde A hasta cada vértice.
BFS cuenta aristas; Dijkstra suma pesos. Dijkstra no funciona con pesos negativos.
El resultado es el camino más corto desde A hasta cada vértice. BFS cuenta aristas; Dijkstra suma pesos. Dijkstra no funciona con pesos negativos.