Función: Algoritmo de DijkstraVolver

Descripción

Aplica el algoritmo de Dijkstra a grafos ponderados conexos o digrafos fuertemente conexos.

Si el grafo no es ponderado, se tomarán las aristas con peso igual a 1 y la ausencia de ellas como infinito

Cadena de entrada

gr_dijkstra

Cadena de salida

GRAFO.dijkstra

Uso

gr_dijkstra(<grafo>,<nodo1>[,<nodo2>])

Parámetros
#	Parámetro	Descripción	Valor por defecto
1	grafo	Diccionario válido de grafo
2	nodo1	Nodo inicial del camino, dado por índice o etiqueta
3	nodo2	Nodo final del camino, dado por índice o etiqueta. Si no se especifica, se obtiene el camino de `nodo1` a los demás nodos	∅

Valor devuelto

Si se especifican ambos nodos, un diccionario con claves camino y distancia
Si se especifica el nodo de inicio, un vector de diccionarios como el anterior, desde el nodo de inicio a cada nodo en orden de índice

Ejemplos

Grafo de 8 nodos ponderado-positivo conexo:

gr_nuevo([[inf,3,1,inf,inf,inf,inf,inf],[3,inf,inf,1,inf,inf,5,inf],[1,inf,inf,2,inf,5,inf,inf],[inf,1,2,inf,4,2,inf,inf],[inf,inf,inf,4,inf,inf,2,1],[inf,inf,5,2,inf,inf,inf,3],[inf,5,inf,inf,2,inf,inf,inf],[inf,inf,inf,inf,1,3,inf,inf]],['A','B','C','D','E','F','G','H'],falso,verdadero)

Salida en JMEScriptGUI con visor de grafos v0.1:

Camino y distancia entre nodos 0 y 4:

gr_dijkstra(gr_nuevo([[inf,3,1,inf,inf,inf,inf,inf],[3,inf,inf,1,inf,inf,5,inf],[1,inf,inf,2,inf,5,inf,inf],[inf,1,2,inf,4,2,inf,inf],[inf,inf,inf,4,inf,inf,2,1],[inf,inf,5,2,inf,inf,inf,3],[inf,5,inf,inf,2,inf,inf,inf],[inf,inf,inf,inf,1,3,inf,inf]],['A','B','C','D','E','F','G','H'],falso,verdadero),0,4)

Diccionario: { 'camino': [0,2,3,4] 'distancia': 7 }

Camino y distancia de todos los nodos al 'H' (7):

VectorEvaluado: [{'camino'=[7,4,3,2,0], 'distancia'=8}, {'camino'=[7,4,3,1], 'distancia'=6}, {'camino'=[7,4,3,2], 'distancia'=7}, {'camino'=[7,4,3], 'distancia'=5}, {'camino'=[7,4], 'distancia'=1}, {'camino'=[7,5], 'distancia'=3}, {'camino'=[7,4,6], 'distancia'=3}, {'camino'=[7], 'distancia'=0}]

Digrafo de 5 nodos ponderado-positivo fuertemente conexo:

gr_nuevo([[inf,7,inf,inf,1],[inf,inf,inf,8,9],[5,2,inf,inf,inf],[1,inf,3,inf,inf],[inf,inf,7,2,inf]],verdadero,verdadero)

Salida en JMEScriptGUI con visor de grafos v0.1:

Camino y distancia entre nodos 'v1' y 'v2':

gr_dijkstra(gr_nuevo([[inf,7,inf,inf,1],[inf,inf,inf,8,9],[5,2,inf,inf,inf],[1,inf,3,inf,inf],[inf,inf,7,2,inf]],verdadero,verdadero),'v1','v2')

Diccionario: { 'camino': [1,3,2] 'distancia': 11 }

Camino y distancia de todos los nodos al 4:

gr_dijkstra(gr_nuevo([[inf,7,inf,inf,1],[inf,inf,inf,8,9],[5,2,inf,inf,inf],[1,inf,3,inf,inf],[inf,inf,7,2,inf]],verdadero,verdadero),4)

VectorEvaluado: [{'camino'=[4,3,0], 'distancia'=3}, {'camino'=[4,3,2,1], 'distancia'=7}, {'camino'=[4,3,2], 'distancia'=5}, {'camino'=[4,3], 'distancia'=2}, {'camino'=[4], 'distancia'=0}]

Véase también…

gr_floydwar

Desde / Última modificación

v0.6.2.0