Calculadora de ruta mínima en grafos ponderados
Busca una ruta de coste-más largo a través de un pequeño gráfico de borde dirigido o no dirigido con costes no negativos.
SU CÁLCULO
Resultado
—
Pasos del cálculo
Trabaje a través de un paso a la vez o revele el cálculo completo. Los pasos utilizan sus entradas actuales.
Cómo calcular
Construir listas de asistencia y utilizar el algoritmo de Dijkstra para resolver el nodo no alcanzado a un costo más largo. Mantener a los predecesores para recuperar una ruta más corta.
Relax edge u→v when distance(u)+cost(u,v)<distance(v)
Ejemplo resuelto
Con los bordes A→B=4, A→C=1, C→B=2, B→D=1, C→D=5, la ruta más corta A-to-D es A → C → B → D a un coste total 4.
Suposiciones y detalles de entrada
Uno a doscientos bordes y a lo sumo 100 nodos sensibles al caso; etiquetas a más de 40 caracteres. Los costes no son negativos y comparten su significado / unidad elegido; se permiten bordes cero y bordes paralelos. El comienzo y el destino deben ocurrir en la lista de bordes. Los costes negativos, las hojas de ruta, los tiempos de viaje en directo y las restricciones de giro no se apoyan. Cuando las rutas se cortan, se retiene una ruta desde el orden de entrada, sin enumerar cada camino atado. Se informa explícitamente de un destino inalcanzable.
Usando esta calculadora
¿Puedo entrar en mi propio problema?
Sí. Sustitúyase los valores de ejemplo por sus propias entradas. El resultado, los pasos de cálculo, los cuadros y los diagramas aplicables se actualizan a partir de esos insumos. Los valores blanks o inválidos despejan el resultado; los valores de ejemplo nunca se sustituyen silenciosamente por los insumos que faltan.
¿Los resultados son exactos?
Los resultados utilizan la aritmética de un punto flotante y se muestran redondeados. Leer la fórmula, suposiciones y cualquier precisión de los datos antes de interpretar el resultado.
¿Mi entrada está cargada?
El cálculo se ejecuta en su navegador. No se requiere cuenta, carga de archivos o servicio AI externo. Las entradas no se guardan entre recargas de página.
Calcular los tiempos de tareas más tempranos y más recientes, el total de tareas de slack y críticas en una red de dependencia.
Planear una secuencia de distancias, velocidades medias y roturas con fechas de llegada.
Calcular los bloques asignados y el desguace interno para una lista de tamaños de archivos lógicos y una unidad de asignación elegida.
Espacio reservado para publicidad.