Qué resuelve el panel Shortest path El panel Shortest path ejecuta cuatro algoritmos sobre el mismo grafo ponderado: Dijkstra, A*, Bellman–Ford y Floyd–Warshall. Cada conjunto de filas nombra su método, imprime la distancia y la ruta y — para las dos búsquedas de fuente única que trazan — el orden de asentamiento en que se finalizaron los vértices. Los grafos se construyen en el banco de teoría de grafos compartido; el conmutador Directed, los pesos de las aristas y la caja de pegado de la matriz de adyacencia se aplican todos.
Cómo ejecutar cada algoritmo 01 Carga un grafo y fija los extremos. Construye un preajuste o pega una matriz de adyacencia, luego elige Source y Target; una construcción con preajuste los restablece al primer y último nodo. 02 Dijkstra responde distancia, camino y orden de asentamiento, y rechaza cualquier grafo con una arista negativa — el error nombra la arista y apunta a Bellman–Ford. 03 A\ añade un selector de heurística (manhattan / euclidean / zero) e informa los nodos expandidos frente a Dijkstra, la escala de heurística realmente usada y si la heurística es consistente y por tanto óptima. 04 Bellman–Ford informa las rondas de relajación, lista las distancias finales por nodo y marca un ciclo negativo si existe. 05 Floyd–Warshall llena la matriz de distancias desde una fuente, marca los nodos de ciclo negativo y puede responder cualquier par origen/destino mediante la misma tabla.
Lecturas resueltas Leído del panel:
Configuración
Lectura
Grafo predeterminado de 6 nodos, Dijkstra A → F
distancia 13 ; camino A → C → B → D → E → F ; orden de asentamiento A → C → B → D → E → F ; d[B] 3 , d[C] 2 , d[D] 8 , d[E] 10
Rejilla 4 × 5, Dijkstra 1-1 → 4-5
distancia 7 ; el orden de asentamiento lista los 20 nodos; camino 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5
Grafo predeterminado, A* con euclidean
distancia 13 , mismo camino; nodos expandidos 6 / Dijkstra 6 ; escala de heurística 0.01346 ; consistente óptima Yes
Preajuste Negative weights, Bellman–Ford desde S
3 rondas de relajación; d[S] 0 , d[A] 3 , d[B] 5 , d[C] 0 , d[D] 3 ; ciclo negativo None
Preajuste Negative weights, Floyd–Warshall S → D
distancia 3 ; camino S → B → A → C → D ; nodos de ciclo negativo None
El d[C] = 2 de Dijkstra viene de la arista directa A–C, y d[B] = 3 de A → C → B, no de la arista más pesada A–B de peso 4 . Bellman–Ford alcanza los mismos valores en un grafo con una arista −3, y Floyd–Warshall encuentra S → B → A → C → D encadenando una arista negativa y una positiva.
Por qué A\* imprime una escala Las coordenadas del lienzo y los pesos de las aristas son cantidades distintas, así que A* mide la heurística sobre el trazado y la escala por el mayor factor que aún mantiene h(u) ≤ w(u,v) + h(v) en cada arco. En el grafo predeterminado la escala euclidean es 0.01346 , y las tres heurísticas expanden los mismos 6 nodos que Dijkstra. La fila de consistente-óptima es la promesa de que la distancia devuelta es exacta.
Límites
Pesos no negativos para Dijkstra y A\*. Ambos rechazan una arista negativa en vez de devolver una distancia demasiado grande; cambia a Bellman–Ford en el mismo panel para el preajuste Negative weights. Una fuente por ejecución. No hay Dijkstra multi-fuente ni Johnson para todos los pares; Floyd–Warshall es la opción de todos los pares, con coste cúbico. El panel tampoco lee listas de aristas de un archivo ni exporta una ruta — escribe la matriz de adyacencia en el espacio de trabajo y llévala a las matrix tools , al panel Spanning tree para el cableado más barato o a Flow & matching para preguntas de capacidad.
La frontera de las aristas negativas Construye el preajuste Negative weights (S → A 4, S → B 5, A → C −3, B → A −2, B → C 4, C → D 3) y pulsa Dijkstra con Source S. El panel se niega con el mensaje "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" en lugar de un número incorrecto plausible. Cambia el algoritmo a Bellman–Ford y S → C lee 0 , una distancia que el asentamiento codicioso de Dijkstra nunca habría producido. A* lleva el mismo rechazo; su mensaje también apunta a Bellman–Ford.
Dónde resulta útil Prueba de optimalidad para un recorrido El orden de asentamiento de Dijkstra es la prueba de que las distancias finales son correctas: cada vértice se finaliza una vez y nunca se revisita. En el grafo predeterminado la arista directa A–B pesa 4 , pero la ruta por C cuesta 3 , y el orden A → C → B → D → E → F muestra C finalizado antes que B — el panel exhibe su propio argumento de corrección.
Enseñar por qué las heurísticas deben escalarse Pon A* en la heurística zero y la ejecución es Dijkstra con contabilidad (escala 1 ); pon euclidean en el grafo predeterminado trazado y la escala baja a 0.01346 , así que la estimación nunca puede superar el coste real mientras la ruta sigue siendo exacta.
Costes negativos en planificación El preajuste Negative weights modela un crédito entre dos etapas. Bellman–Ford responde S → D en 3 ; Floyd–Warshall confirma el mismo valor, y ninguno informa un ciclo negativo, así que la cadena de mejora S → B → A → C → D termina.
Privacidad La edición del grafo y cada ejecución de shortest path ocurren en tu navegador; no se sube nada.
Referencias
Wikipedia, Dijkstra's algorithm , en.wikipedia.org (访问日期:2026-10-07)— asentamiento codicioso y pesos no negativos.
Wikipedia, Bellman–Ford algorithm , en.wikipedia.org (访问日期:2026-10-07)— rondas de relajación y detección de ciclos negativos.
Wikipedia, Floyd–Warshall algorithm , en.wikipedia.org (访问日期:2026-10-07)— programación dinámica para todos los pares.
Wikipedia, A* search algorithm , en.wikipedia.org (访问日期:2026-10-07)— heurísticas admisibles y consistentes.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— caminos más cortos de fuente única.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07