Camino mínimo

En un grafo pesado cualquiera, podemos buscar el camino mínimo entre dos nodos dados. Es decir, el camino que empiece en $v$ y termine en $w$ tal que la longitud del mismo sea la mínima, al que se lo denota habitualmente como $C^{0}$ . En matematico eso seria:

C^{0} = m i n (\sum_{e \in p (v, w)} l (e))

Donde $p (v, w)$ es el conjunto de todos los caminos existentes entre $v$ y $w$ .

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 ===|3| id2
id1 ---|11| id3
id2 ---|5| id3
id2 ===|2| id4
id3 ---|3| id5
id4 ===|5| id5

En el dibujo de arriba se ve un grafo pesado, donde esta marcado el camino mínimo entre el nodo 1 y el nodo 5.

El concepto de camino mínimo puede ser empleado tanto en grafos como en dígrafos, pero segun cual estemos planteando podemos necesitar datos concretos de la estructura.

Por ejemplo, si quisieramos encontrar el camino mínimo de un nodo cualquiera a otro en un grafo, podria pasar que sea imposible llegar. Quizas el grafo tiene mas de una componente conexa, y los nodos pedidos se encuentran cada uno en una distinta. En ese caso, definimos el camino mínimo tendria longitud $\infty$ .

Por otro lado, si hablamos de un dígrafo, por mas que sepamos que se trata de una unica componente conexa, es posible que existan nodos imposibles de llegar entre si. Esto se debe a las posibles direcciones que las aristas pueden tener. Por ejemplo, si un nodo tiene grado de entrada igual a 0, entonces nadie puede llegar a dicho nodo.

Algo importante a tener en cuenta, es que si queremos buscar un camino mínimo en un grafo (orientado o no) necesitamos que dicho grafo no tenga aristas con pesos negativos. Si nuestro grafo tiene una arista con peso negativo, y nosotros lo que queremos es minimizar la distancia entre un nodo y otro, podriamos ir y venir por ese nodo que resta y minimizarlo hasta el infinito, lo cual no tendria sentido.

Existen muchos algoritmos para la busqueda de camino mínimo. En particular vamos a ver dos: el algoritmo de Dijkstra y el algoritmo de Ford. El primero sirve tanto para grafos como para dígrafos, pero no si tienen aristas de peso negativo. El segundo algoritmo es exclusivo de dígrafos, pero aparte de encontrar el camino mínimo, es capaz de distinguir si el dígrafo ingresado tiene o no un loop con peso negativo.