Camino mínimo en un grafo
Calcula la distancia mínima entre nodos con pesos no negativos.
Camino mínimo en un grafo: magnitud y alcance
Calcula la distancia mínima entre nodos con pesos no negativos.
Dijkstra mantiene para cada nodo la mejor distancia conocida desde el origen y relaja una arista cuando d(u)+w mejora d(v).
La distancia inicial del origen es cero y las demás empiezan como infinito. Al visitar 0 se fija d(1)=3; al visitar 1 se propone d(2)=7. Como no hay alternativa menor, 7 queda definitivo.
Fórmula d(v)=min(d(v),d(u)+w(u,v)).
Los pesos deben ser no negativos; con pesos negativos, fijar un nodo demasiado pronto puede ocultar una ruta posterior mejor.
Campos visibles: Aristas dirigidas origen,destino,peso separadas por ; Nodo de origen; Nodo de destino. d(v)=min(d(v),d(u)+w(u,v)).
Ejemplo numérico: Distancia mínima hasta el nodo 2 = 7.
Aristas dirigidas origen,destino,peso separadas por punto y coma (;): «0,1,3;1,2,4»; Nodo de origen: «0»; Nodo de destino: «2».
En 0→1 con peso 3 y 1→2 con peso 4, la distancia dirigida de 0 a 2 es 7.
Resultado completo: Distancia mínima hasta el nodo 2 = 7.
Lectura matemática de Distancia mínima hasta el nodo 2
Las aristas son dirigidas: escribir 0,1,3 no crea automáticamente 1→0. Origen y destino se eligen por separado.
La ruta y la distancia son conceptos distintos. Esta salida resume el coste hasta el destino; en un grafo con varias rutas de igual coste podrían existir caminos mínimos diferentes.
Restricciones propias de camino mínimo en un grafo
Se admiten hasta 500 nodos y 2000 aristas. Un destino sin camino produce error en vez de una distancia inventada.
Aristas duplicadas pueden ofrecer pesos distintos y la relajación conserva el menor efecto. Los identificadores son etiquetas enteras no negativas, no distancias ni posiciones geométricas.
Fuentes y referencias
Continúa con estas herramientas
Preguntas frecuentes
¿Qué advertencia debe acompañar a distancia mínima hasta el nodo 2?
Los pesos negativos y los nodos sin ruta se rechazan con un error explícito.
¿Qué representan los controles «Aristas dirigidas origen,destino,peso separadas por punto y coma (;); Nodo de origen; Nodo de destino»?
El formato de entrada es origen,destino,peso separado por punto y coma; origen y destino se eligen en controles propios. Cada valor ocupa la posición indicada por la fórmula d(v)=min(d(v),d(u)+w(u,v)).
¿Cómo se llega a Distancia mínima hasta el nodo 2 = 7.?
Con Aristas dirigidas origen,destino,peso separadas por punto y coma (;): «0,1,3;1,2,4»; Nodo de origen: «0»; Nodo de destino: «2», se sustituyen las magnitudes en d(v)=min(d(v),d(u)+w(u,v)). El cálculo da Distancia mínima hasta el nodo 2 = 7.
¿Qué entradas quedan fuera del dominio de camino mínimo en un grafo?
Los identificadores de nodo deben ser enteros no negativos y los pesos no negativos. Admite hasta 500 nodos y 2000 aristas dirigidas. El origen y el destino deben aparecer en el grafo y estar conectados por un camino dirigido.
¿Cómo debe leerse la salida de camino mínimo en un grafo?
Las aristas son dirigidas y la salida identifica la distancia mínima entre los dos nodos seleccionados.
Herramienta de OCC Tools