LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

 búsqueda de amplitud lexicográfica o Lex-BFS es un algoritmo de tiempo lineal para ordenar los vértices de un gráfico . El algoritmo es diferente de una búsqueda de amplitud , pero produce un orden consistente con la búsqueda de amplitud.

El algoritmo de búsqueda de amplitud lexicográfica se basa en la idea del refinamiento de la partición y fue desarrollado por primera vez por Donald J. Rose, Robert E. Tarjan y George S. Lueker ( 1976 ). Corneil (2004) presenta una encuesta más detallada del tema . Se ha utilizado como una subrutina en otros algoritmos gráficos, incluido el reconocimiento de gráficos cordales y la coloración óptima de gráficos hereditarios a distancia .

Fondo [ editar ]

El algoritmo de búsqueda de amplitud primero se define comúnmente mediante el siguiente proceso:

• Inicialice una cola de vértices del gráfico, con el vértice inicial del gráfico como único elemento de la cola.
• Mientras que la cola no está vacía, elimine (elimine) un vértice v de la cola y agregue a la cola (coloque en cola) todos los otros vértices a los que puede llegar un borde desde v que aún no se han agregado en los pasos anteriores.

Sin embargo, en lugar de definir el vértice para elegir en cada paso de manera imperativa como el producido por la operación de retirada de una cola, se puede definir la misma secuencia de vértices declarativamente por las propiedades de estos vértices. Es decir, una búsqueda estándar de amplitud es solo el resultado de aplicar repetidamente esta regla:

• Produzca repetidamente un vértice v , eligiendo en cada paso un vértice v que aún no se haya elegido y que tenga un predecesor (un vértice que tenga un borde hacia v ) lo más temprano posible en la salida.

En algunos casos, este orden de vértices por las posiciones de salida de sus predecesores puede tener vínculos: dos vértices diferentes tienen el mismo predecesor más temprano. En este caso, el orden en que se eligen esos dos vértices puede ser arbitrario. El resultado de la búsqueda lexicográfica de amplitud primera difiere de una búsqueda de amplitud estándar en tener una regla consistente para romper tales lazos. En la búsqueda de amplitud lexicográfica, el orden de salida es el orden que produciría la regla:

• Produzca repetidamente un vértice v , eligiendo en cada paso un vértice v que aún no ha sido elegido y cuyo conjunto completo de predecesores ya es lo más pequeño posible en orden lexicográfico .

Entonces, cuando dos vértices v y w tienen el mismo predecesor más temprano, antes que cualquier otro vértice no elegido, el algoritmo de búsqueda de amplitud estándar los ordenará arbitrariamente. En cambio, en este caso, el algoritmo LexBFS elegiría entre v y w mediante el orden de salida de sus segundos predecesores más antiguos. Si solo uno de ellos tiene un segundo predecesor más antiguo que ya se ha emitido, se elige ese. Si tanto v como w tienen el mismo segundo predecesor más temprano, entonces el empate se rompe al considerar sus terceros predecesores más antiguos, y así sucesivamente.

Aplicar esta regla directamente comparando vértices de acuerdo con esta regla conduciría a un algoritmo ineficiente. En cambio, la búsqueda lexicográfica de amplitud primero utiliza una estructura de datos de partición establecida para producir el mismo orden de manera más eficiente, al igual que una búsqueda estándar de amplitud utiliza una estructura de datos de cola para producir su ordenamiento eficientemente.

Algoritmo [ editar ]

El algoritmo de búsqueda de amplitud lexicográfica reemplaza la cola de vértices de una búsqueda de amplitud estándar con una secuencia ordenada de conjuntos de vértices. Los conjuntos en la secuencia forman una partición de los vértices restantes. En cada paso, un vértice v del primer conjunto de la secuencia se elimina de ese conjunto, y si esa eliminación hace que el conjunto se vacíe, el conjunto se eliminará de la secuencia. Luego, cada conjunto de la secuencia se reemplaza por dos subconjuntos: los vecinos de v y los no vecinos de v . El subconjunto de vecinos se coloca antes en la secuencia que el subconjunto de no vecinos. En pseudocódigo , el algoritmo se puede expresar de la siguiente manera:

• Inicialice una secuencia Σ de conjuntos, para contener un único conjunto que contenga todos los vértices.
• Inicialice la secuencia de salida de vértices para que esté vacía.
• Mientras Σ no está vacío:
  • Encuentra y elimina un vértice v del primer conjunto en Σ
  • Si el primer conjunto en Σ ahora está vacío, quítelo de Σ
  • Agregue v al final de la secuencia de salida.
  • Para cada borde vw tal que w todavía pertenece a un conjunto S en Σ:
    • Si el conjunto S que contiene w aún no se ha reemplazado mientras procesaba v , cree un nuevo conjunto de reemplazo vacío T y colóquelo antes de S en la secuencia; de lo contrario, vamos a T como el conjunto antes de la S .
    • Mueva w de S a T , y si esto hace que S se vacíe, elimine S de Σ.

Cada vértice se procesa una vez, cada borde se examina solo cuando se procesan sus dos puntos finales y (con una representación apropiada para los conjuntos en Σ que permite que los elementos se muevan de un conjunto a otro en tiempo constante) cada iteración del bucle interno toma solo tiempo constante. Por lo tanto, al igual que los algoritmos de búsqueda de gráficos más simples, como la búsqueda de amplitud y la búsqueda de profundidad , este algoritmo requiere tiempo lineal.

El algoritmo se llama búsqueda lexicográfica de amplitud porque el orden que produce es un orden que también podría haber sido producido por una búsqueda de amplitud, y porque si el orden se usa para indexar las filas y columnas de una matriz de adyacencia de un gráfico entonces el algoritmo ordena las filas y columnas en orden lexicográfico .

Aplicaciones [ editar ]

Gráficos cordales [ editar ]

Un gráfico G se define como cordal si sus vértices tienen un orden de eliminación perfecto , un orden tal que para cualquier vértice v los vecinos que ocurren más adelante en el orden forman una camarilla. En un gráfico cordal, el reverso de un ordenamiento lexicográfico es siempre un ordenamiento de eliminación perfecto. Por lo tanto, uno puede probar si un gráfico es cordal en tiempo lineal mediante el siguiente algoritmo:

• Use la búsqueda lexicográfica de amplitud primero para encontrar un orden lexicográfico de G
• Para cada vértice v :
  • Sea w el vecino de v que ocurre antes de v , tan cerca de v en la secuencia como sea posible
    • (Continúe con el siguiente vértice v si no existe tal w )
  • Si el conjunto de vecinos anteriores de v (excluyendo w ) no es un subconjunto del conjunto de vecinos anteriores de w , el gráfico no es cordal
• Si el ciclo termina sin mostrar que el gráfico no es cordal, entonces es cordal.

Esta aplicación fue la motivación original que llevó a Rose, Tarjan y Lueker (1976) a desarrollar el algoritmo de búsqueda lexicográfica de primera amplitud. ^[1]

Coloración de gráficos [ editar ]

Se dice que un gráfico G es perfectamente ordenable si hay una secuencia de sus vértices con la propiedad de que, para cualquier subgrafía inducida de G , un algoritmo de coloración codicioso que colorea los vértices en el orden de secuencia inducida garantiza una coloración óptima.

Para un gráfico cordal, un orden de eliminación perfecto es un orden perfecto: el número del color utilizado para cualquier vértice es el tamaño de la camarilla formada por él y sus vecinos anteriores, por lo que el número máximo de colores utilizado es igual al tamaño de la camarilla más grande en el gráfico, y ninguna coloración puede usar menos colores. Una subgrafía inducida de un gráfico cordal es cordal y la subsecuencia inducida de su ordenación de eliminación perfecta es una ordenación de eliminación perfecta en el subgrafo, por lo que los gráficos cordales son perfectamente ordenables, y la búsqueda lexicográfica de amplitud puede usarse para colorearlos de manera óptima.

La misma propiedad es cierta para una clase más grande de gráficos, los gráficos hereditarios de distancia: los gráficos hereditarios de distancia son perfectamente ordenables, con un ordenamiento perfecto dado por el reverso de un ordenamiento lexicográfico, por lo que la búsqueda lexicográfica de amplitud puede usarse en conjunto con algoritmos de coloración codiciosos para colorearlos de manera óptima en tiempo lineal. ^[2]

Otras aplicaciones [ editar ]

Bretscher y col. (2008) describen una extensión de la búsqueda lexicográfica de amplitud que rompe cualquier vínculo adicional utilizando el gráfico complementario del gráfico de entrada. Como muestran, esto se puede usar para reconocer los coógrafos en tiempo lineal. Habib y col. (2000) describen aplicaciones adicionales de búsqueda lexicográfica de amplitud que incluye el reconocimiento de gráficos de comparabilidad y gráficos de intervalo .

Pedidos de LexBFS [ editar ]

Se dice que una enumeración de los vértices de un gráfico es un pedido de LexBFS si es el posible resultado de la aplicación de LexBFS a este gráfico.

Dejar $${\ displaystyle G = (V, E)} ser un gráfico con $${\ displaystyle n}vértices Recordar que$${\ displaystyle N (v)} es el conjunto de vecinos de $${\ displaystyle v}. Dejar$${\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {n})} ser una enumeración de los vértices de $${\ displaystyle V}. La enumeración$${\ displaystyle \ sigma} es un pedido de LexBFS (con fuente $${\ displaystyle v_ {1}}) si, para todos {\ displaystyle 1 \ leq i  con $${\ displaystyle v_ {i} \ en N (v_ {j}) \ setminus N (v_ {k})}, existe {\ displaystyle m  tal que $${\ displaystyle v_ {m} \ en N (v_ {j}) \ setminus V (v_ {k})}.

Algoritmo de Dijkstra (o ruta más corta de Dijkstra primer algoritmo , algoritmo SPF ) ^[1] es un algoritmo para la búsqueda de las rutas más cortas entre los nodos en un gráfico , que puede representar, por ejemplo, redes de carreteras . Fue concebido por el informático Edsger W. Dijkstra en 1956 y publicado tres años después. ^{[2] [3] [4]}

El algoritmo existe en muchas variantes. El algoritmo original de Dijkstra encontró la ruta más corta entre dos nodos dados, ^[4] pero una variante más común fija un solo nodo como el nodo "fuente" y encuentra las rutas más cortas desde la fuente a todos los demás nodos en el gráfico, produciendo una ruta más corta árbol .

Para un nodo fuente dado en el gráfico, el algoritmo encuentra la ruta más corta entre ese nodo y todos los demás. ^{[5] : 196–206} También se puede usar para encontrar las rutas más cortas desde un solo nodo a un solo nodo de destino deteniendo el algoritmo una vez que se ha determinado la ruta más corta al nodo de destino. Por ejemplo, si los nodos del gráfico representan ciudades y los costos de la ruta de borde representan distancias de conducción entre pares de ciudades conectadas por una carretera directa (por simplicidad, ignore las luces rojas, las señales de alto, las carreteras de peaje y otras obstrucciones), se puede usar el algoritmo de Dijkstra para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Una aplicación ampliamente utilizada del algoritmo de ruta más corta son los protocolos de enrutamiento de red , especialmente IS-IS(Sistema intermedio a sistema intermedio) y Abrir primero la ruta más corta ( OSPF ). También se emplea como una subrutina en otros algoritmos como el de Johnson .

El algoritmo de Dijkstra usa etiquetas que son enteros positivos o números reales, que están totalmente ordenados. Se puede generalizar el uso de cualquier etiqueta que esté parcialmente ordenada, siempre que las etiquetas posteriores (se produzca una etiqueta posterior al atravesar un borde) no disminuyan de forma monotónica. Esta generalización se denomina algoritmo genérico de la ruta más corta de Dijkstra. ^[6]

El algoritmo original de Dijkstra no usa una cola de prioridad mínima y se ejecuta a tiempo $${\ displaystyle O (| V | ^ {2})} (dónde $${\ displaystyle | V |}es el número de nodos) La idea de este algoritmo también se da en Leyzorek et al. 1957 . La implementación basada en una cola de prioridad mínima implementada por un montón de Fibonacci y ejecutándose en$${\ displaystyle O (| E | + | V | \ log | V |)} (dónde $${\ displaystyle | E |}es el número de aristas) se debe a Fredman y Tarjan 1984 . Este es asintóticamente el algoritmo de ruta más corta de fuente única más rápido conocido para gráficos arbitrarios dirigidos con pesos no negativos no acotados. Sin embargo, los casos especializados (como los pesos acotados / enteros, los gráficos acíclicos dirigidos, etc.) pueden mejorarse aún más como se detalla en las variantes especializadas .

En algunos campos la inteligencia artificial en particular, el algoritmo de Dijkstra o una variante del mismo se conoce como búsqueda de costo uniforme y se formula como una instancia de la idea más general de la mejor búsqueda en primer lugar .

Algoritmo de Dijkstra

Algoritmo de Dijkstra para encontrar el camino más corto entre a y b . Selecciona el vértice no visitado con la distancia más baja, calcula la distancia a través de él a cada vecino no visitado y actualiza la distancia del vecino si es más pequeño. Mark visitó (configurado en rojo) cuando terminó con los vecinos.
Clase	Algoritmo de búsqueda
Estructura de datos	Grafico
El peor de los casos	$${\ displaystyle O (| E | + | V | \ log | V |)}

Historia [ editar ]

¿Cuál es la forma más corta de viajar de Rotterdam a Groninga , en general: de una ciudad a otra? Es el algoritmo para el camino más corto , que diseñé en unos veinte minutos. Una mañana estaba de compras en AmsterdamCon mi joven prometida, y cansados, nos sentamos en la terraza del café a tomar una taza de café y estaba pensando si podría hacer esto, y luego diseñé el algoritmo para el camino más corto. Como dije, fue un invento de veinte minutos. De hecho, fue publicado en el '59, tres años después. La publicación aún es legible, de hecho, es bastante agradable. Una de las razones por las que es tan agradable fue que lo diseñé sin lápiz ni papel. Más tarde supe que una de las ventajas de diseñar sin lápiz y papel es que casi estás obligado a evitar todas las complejidades evitables. Finalmente, ese algoritmo se convirtió, para mi gran asombro, en uno de los pilares de mi fama.

-  Edsger Dijkstra, en una entrevista con Philip L. Frana, Comunicaciones de la ACM, 2001 ^[3]

Dijkstra pensó en el problema del camino más corto cuando trabajaba en el Centro de Matemáticas de Amsterdam en 1956 como programador para demostrar las capacidades de una nueva computadora llamada ARMAC. ^[8] Su objetivo era elegir tanto un problema como una solución (que sería producida por computadora) que las personas que no son informáticas pudieran entender. Diseñó el algoritmo de ruta más corta y luego lo implementó para ARMAC para un mapa de transporte ligeramente simplificado de 64 ciudades en los Países Bajos (64, de modo que 6 bits serían suficientes para codificar el número de ciudad). ^[3]Un año después, se encontró con otro problema de los ingenieros de hardware que trabajaban en la próxima computadora del instituto: minimizar la cantidad de cable necesario para conectar los pines en el panel posterior de la máquina. Como solución, volvió a descubrir el algoritmo conocido como algoritmo de árbol de expansión mínima de Prim (conocido anteriormente por Jarník , y también redescubierto por Prim ). ^[9] [10] Dijkstra publicó el algoritmo en 1959, dos años después de Prim y 29 años después de Jarník. ^[11] [12]

Algoritmo [ editar ]

Ilustración del algoritmo de Dijkstra encontrando una ruta desde un nodo de inicio (abajo a la izquierda, rojo) a un nodo de meta (arriba a la derecha, verde) en un problema de planificación de movimiento del robot Los nodos abiertos representan el conjunto "tentativo" (también conocido como conjunto de nodos "no visitados"). Los nodos rellenos son visitados, y el color representa la distancia: cuanto más verde, más cerca. Los nodos en todas las diferentes direcciones se exploran de manera uniforme, apareciendo más o menos como un frente de onda circular, ya que el algoritmo de Dijkstra utiliza una heurística idénticamente igual a 0.

Deje que el nodo en el que estamos comenzando se llame el nodo inicial . Deje que la distancia de nodo Y sea la distancia desde el nodo inicial a Y . El algoritmo de Dijkstra asignará algunos valores de distancia iniciales e intentará mejorarlos paso a paso.

1. Marque todos los nodos sin visitar. Cree un conjunto de todos los nodos no visitados llamado conjunto no visitado .
2. Asigne a cada nodo un valor de distancia tentativo: ajústelo a cero para nuestro nodo inicial y al infinito para todos los demás nodos. Establecer el nodo inicial como actual. ^[13]
3. Para el nodo actual, considere todos sus vecinos no visitados y calcule sus distancias provisionales a través del nodo actual. Compare la distancia tentativa recién calculada con el valor asignado actual y asigne el más pequeño. Por ejemplo, si el nodo actual A está marcado con una distancia de 6, y el borde que lo conecta con un vecino B tiene una longitud 2, entonces la distancia de B a A será 6 + 2 = 8. Si B se marcó previamente con una distancia mayor que 8 y luego cámbiela a 8. De lo contrario, mantenga el valor actual.
4. Cuando hayamos terminado de considerar todos los vecinos no visitados del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado . Un nodo visitado nunca se volverá a comprobar.
5. Si el nodo de destino se ha marcado como visitado (cuando se planifica una ruta entre dos nodos específicos) o si la distancia tentativa más pequeña entre los nodos en el conjunto no visitado es infinito (cuando se planifica un recorrido completo; ocurre cuando no hay conexión entre el nodo inicial y los nodos restantes no visitados), luego deténgase. El algoritmo ha terminado.
6. De lo contrario, seleccione el nodo no visitado que está marcado con la distancia tentativa más pequeña, configúrelo como el nuevo "nodo actual" y vuelva al paso 3.

Al planificar una ruta, en realidad no es necesario esperar hasta que el nodo de destino sea "visitado" como se indicó anteriormente: el algoritmo puede detenerse una vez que el nodo de destino tenga la menor distancia tentativa entre todos los nodos "no visitados" (y por lo tanto podría seleccionarse como el siguiente "actual").

Descripción [ editar ]

Nota: Para facilitar la comprensión, esta discusión utiliza los términos intersección , carretera y mapa ; sin embargo, en terminología formal, estos términos son vértice , borde y gráfico , respectivamente.

Suponga que desea encontrar la ruta más corta entre dos intersecciones en un mapa de la ciudad: un punto de partida y un destino . El algoritmo de Dijkstra inicialmente marca la distancia (desde el punto de partida) a cualquier otra intersección en el mapa con infinito . Esto se hace no para implicar que hay una distancia infinita, sino para notar que esas intersecciones aún no se han visitado. Algunas variantes de este método dejan las distancias de las intersecciones sin etiquetar . Ahora seleccione la intersección actual en cada iteración. Para la primera iteración, la intersección actual será el punto de partida, y la distancia a ella (la etiqueta de la intersección) será cero . Para iteraciones posteriores (después de la primera), la intersección actual será una intersección no visitada más cercana punto de partida (esto será fácil de encontrar).

Desde la intersección actual, actualice la distancia a cada intersección no visitada que esté directamente conectada a ella. Esto se hace determinando la suma de la distancia entre una intersección no visitada y el valor de la intersección actual y luego volviendo a etiquetar la intersección no visitada con este valor (la suma) si es menor que el valor actual de la intersección no visitada. En efecto, la intersección se vuelve a etiquetar si la ruta a través de la intersección actual es más corta que las rutas conocidas anteriormente. Para facilitar la identificación del camino más corto, con lápiz, marque el camino con una flecha que apunte a la intersección etiquetada si la etiqueta / reetiqueta, y borre todos los demás que apuntan a ella. Después de haber actualizado las distancias a cadaintersección vecina , marque la intersección actual como visitada y seleccione una intersección no visitada con una distancia mínima (desde el punto de partida), o la etiqueta más baja, como la intersección actual. Las intersecciones marcadas como visitadas están etiquetadas con la ruta más corta desde el punto de partida hasta el mismo y no se volverán a visitar ni a regresar.

Continúe este proceso de actualización de las intersecciones vecinas con las distancias más cortas, marcando la intersección actual como visitada y avanzando hacia una intersección no visitada más cercana hasta que haya marcado el destino como visitado. Una vez que haya marcado el destino como visitado (como es el caso con cualquier intersección visitada), ha determinado la ruta más corta desde el punto de partida y puede seguir su camino hacia atrás siguiendo las flechas en reversa . En las implementaciones del algoritmo, esto generalmente se hace (después de que el algoritmo ha alcanzado el nodo de destino) siguiendo a los padres de los nodos desde el nodo de destino hasta el nodo inicial; Es por eso que también hacemos un seguimiento del padre de cada nodo.

Este algoritmo no hace ningún intento de "exploración" directa hacia el destino como cabría esperar. Más bien, la única consideración para determinar la próxima intersección "actual" es su distancia desde el punto de partida. Por lo tanto, este algoritmo se expande hacia afuera desde el punto de partida, considerando interactivamente cada nodo que está más cerca en términos de la distancia de ruta más corta hasta que llega al destino. Cuando se entiende de esta manera, queda claro cómo el algoritmo necesariamente encuentra el camino más corto. Sin embargo, también puede revelar una de las debilidades del algoritmo: su relativa lentitud en algunas topologías.

Pseudocódigo [ editar ]

En el siguiente algoritmo, el código u ← vértice en Q con min dist [u] , busca el vértice u en el conjunto de vértices Q que tiene el menor valor dist [ u ] . length ( u , v ) devuelve la longitud de la unión de borde (es decir, la distancia entre) los dos nodos vecinos u y v . La variable alt en la línea 18 es la longitud de la ruta desde el nodo raíz hasta el nodo vecino v si tuviera que pasar por u . Si esta ruta es más corta que la ruta más corta actual registrada para v, esa ruta actual se reemplaza con esta ruta alternativa . La matriz anterior se rellena con un puntero al nodo "siguiente salto" en el gráfico fuente para obtener la ruta más corta a la fuente.

Una demostración del algoritmo de Dijkstra basado en la distancia euclidiana. Las líneas rojas son la ruta de acceso más corta, es decir, conectando u y prev [ u ]. Las líneas azules indican dónde ocurre el relajamiento, es decir, conectando v con un nodo u en Q , lo que da una ruta más corta desde la fuente a v .

1   función Dijkstra ( Gráfico , fuente ):
 2
 3 crea el conjunto de vértices Q
 4 4
 5       para cada vértice v en Graph :             
 6 dist [ v ] ← INFINITO                  
 7 prev [ v ] ← INDEFINIDO                 
 8 agregue v a Q                       
10 dist [ fuente ] ← 0                        
11      
12       mientras  Q no está vacío:
13           u ← vértice en Q con min dist [u]    
14                                              
15 eliminar u de Q 
dieciséis          
17           para cada vecino v de u :            // solo v que todavía están en Q 
18               alt ← dist [ u ] + longitud ( u , v )
19               si  alt v ]:               
20 dist [ v ] ← alt  
21 anterior [ v ] ← u 
22
23       return dist [], anterior []

Si solo estamos interesados ​​en un camino más corto entre los vértices de origen y destino , podemos terminar la búsqueda después de la línea 15 si u = objetivo . Ahora podemos leer la ruta más corta desde el origen hasta el destino mediante iteración inversa:

1   S ← secuencia vacía
2   u ← objetivo 
3   si se define prev [ u ] o  u = fuente :           // Haga algo solo si se puede alcanzar el vértice 
4       mientras  se define u :                        // Construya la ruta más corta con una pila S 
5 inserte u al principio de S         // Empuje el vértice sobre la pila 
6           u ← anterior [ u ]                            // Atraviese del objetivo al origen

Ahora la secuencia S es la lista de vértices que constituyen una de las rutas más cortas desde el origen hasta el destino , o la secuencia vacía si no existe una ruta.

Un problema más general sería encontrar todas las rutas más cortas entre el origen y el destino (puede haber varios diferentes de la misma longitud). Luego, en lugar de almacenar solo un nodo en cada entrada de prev [] , almacenaríamos todos los nodos que satisfagan la condición de relajación. Por ejemplo, si tanto r como fuente se conectan al objetivo y ambos se encuentran en diferentes caminos más cortos a través del objetivo (porque el costo de borde es el mismo en ambos casos), entonces agregaríamos tanto r como fuente a prev [ target ] . Cuando se completa el algoritmo, anterior []La estructura de datos describirá realmente un gráfico que es un subconjunto del gráfico original con algunos bordes eliminados. Su propiedad clave será que si el algoritmo se ejecutó con algún nodo inicial, entonces cada ruta desde ese nodo a cualquier otro nodo en el nuevo gráfico será la ruta más corta entre esos nodos en el gráfico original, y todas las rutas de esa longitud desde el gráfico original estará presente en el nuevo gráfico. Luego, para encontrar realmente todas estas rutas más cortas entre dos nodos dados, usaríamos un algoritmo de búsqueda de rutas en el nuevo gráfico, como la búsqueda de profundidad primero .

Usar una cola prioritaria [ editar ]

Una cola de prioridad mínima es un tipo de datos abstractos que proporciona 3 operaciones básicas: add_with_priority () , disminución_prioridad () y extract_min () . Como se mencionó anteriormente, el uso de dicha estructura de datos puede conducir a tiempos de cómputo más rápidos que el uso de una cola básica. En particular, el montón de Fibonacci ( Fredman y Tarjan 1984 ) o la cola Brodal ofrecen implementaciones óptimas para esas 3 operaciones. Como el algoritmo es ligeramente diferente, lo mencionamos aquí, también en pseudocódigo:

1   función Dijkstra ( Gráfico , fuente ):
2 dist [ fuente ] ← 0                            // Inicialización
3
4 crear cola de prioridad de vértice Q
5 5
6       para cada vértice v en el gráfico :           
7           si  v ≠ fuente 
8 dist [ v ] ← INFINITO                  // Distancia desconocida desde la fuente a v 
9 anterior [ v ] ← INDEFINIDO                     // Predecesor de v
10
11          Q .add_with_priority ( v , dist [ v ])
12
13
14      mientras  Q no está vacío:                       // El bucle principal 
15          u ← Q .extract_min ()                     // Elimina y devuelve el mejor vértice 
16          para cada vecino v de u :               // solo v que todavía están en Q 
17              alt ← dist [ u ] + longitud ( u , v )
18              si  alt v ]
19 dist [ v ] ← alt 
20 prev [ v ] ← u 
21                  Q .decrease_priority ( v , alt )
22
23      regreso dist, anterior

En lugar de llenar la cola de prioridad con todos los nodos en la fase de inicialización, también es posible inicializarla para contener solo la fuente ; luego, dentro del bloque if alt v ] , el nodo debe insertarse si aún no está en la cola (en lugar de realizar una operación de disminución de prioridad). ^[5] : 198

Se pueden usar otras estructuras de datos para lograr tiempos de cómputo aún más rápidos en la práctica. ^[14]

Prueba de corrección [ editar ]

La prueba del algoritmo de Dijkstra se construye por inducción en el número de nodos visitados.

Hipótesis invariable : Para cada nodo visitado v , dist [v] se considera la distancia más corta desde la fuente hasta v ; y para cada nodo no visitado u , se supone que dist [u] es la distancia más corta cuando viaja a través de nodos visitados únicamente, desde la fuente hasta u . Esta suposición solo se considera si existe una ruta; de lo contrario, la distancia se establece en infinito. (Nota: no asumimos dist [u] es la distancia más corta real para los nodos no visitados)

El caso base es cuando solo hay un nodo visitado, es decir, la fuente del nodo inicial , en cuyo caso la hipótesis es trivial .

De lo contrario, suponga la hipótesis de los nodos visitados n-1 . En cuyo caso, elegimos un borde vu donde u tiene la menor dist [u] de los nodos no visitados y el borde vu es tal que dist [u] = dist [v] + longitud [v, u] . dist [u] se considera la distancia más corta desde la fuente hacia u porque si hubiera una ruta más corta, y si w fuera el primer nodo no visitado en esa ruta, entonces según la hipótesis original dist [w] > dist [u] que crea Una contradicción. Del mismo modo, si hubiera un camino más corto para ustedsin usar nodos no visitados, y si el último pero un nodo en esa ruta fuera w , entonces habríamos tenido dist [u] = dist [w] + longitud [w, u] , también una contradicción.

Después de procesar u seguirá siendo cierto que para cada uno de los nodos no visitados w , dist [w] será la distancia más corta desde la fuente a w utilizando sólo los nodos visitados, porque si había un camino más corto que no vaya por u tendríamos lo encontramos anteriormente, y si hubiera una ruta más corta usando u la habríamos actualizado al procesar u .

Tiempo de ejecución [ editar ]

Los límites del tiempo de ejecución del algoritmo de Dijkstra en un gráfico con aristas E y vértices V se pueden expresar en función del número de aristas, denotado$${\ displaystyle | E |}, y el número de vértices, denotado $${\ displaystyle | V |}, utilizando la notación big-O . Lo apretado que sea un límite depende de la forma en que se implemente el conjunto de vértices Q. A continuación, los límites superiores se pueden simplificar porque$${\ displaystyle | E |} es $${\ displaystyle O (| V | ^ {2})} para cualquier gráfico, pero esa simplificación ignora el hecho de que en algunos problemas, otros límites superiores en $${\ displaystyle | E |} podra celebrar.

Para cualquier implementación del conjunto de vértices Q , el tiempo de ejecución está en

$${\ displaystyle O (| E | \ cdot T _ {\ mathrm {dk}} + | V | \ cdot T _ {\ mathrm {em}}),}

dónde $${\ displaystyle T _ {\ mathrm {dk}}} y $${\ displaystyle T _ {\ mathrm {em}}}son las complejidades de las operaciones de disminución de clave y extracción mínima en Q , respectivamente. La implementación más sencilla del algoritmo de Dijkstra almacena el conjunto de vértices Q como una lista enlazada ordinaria o matriz, y extraer-mínimo es simplemente una búsqueda lineal a través de todos los vértices en Q . En este caso, el tiempo de ejecución es$${\ displaystyle O (| E | + | V | ^ {2}) = O (| V | ^ {2})}.

Debe tenerse en cuenta que si la implementación almacena el gráfico como una lista de adyacencia, el tiempo de ejecución para un gráfico denso, es decir, donde $${\ displaystyle | E |} = $${\ displaystyle O (| V | ^ {2}),} es

$${\ displaystyle \ Theta ((| V | ^ {2}) \ log | V |)}.

Para gráficos dispersos , es decir, gráficos con mucho menos de$${\ displaystyle | V | ^ {2}}bordes, el algoritmo de Dijkstra se pueden implementar de manera más eficiente mediante el almacenamiento de la gráfica en forma de listas de adyacencia y usando un árbol binario de búsqueda auto-equilibrio , pila binaria , el montón de emparejamiento , o montón de Fibonacci como una cola de prioridad para implementar mínimo extraer eficientemente. Para realizar pasos clave de disminución en un montón binario de manera eficiente, es necesario utilizar una estructura de datos auxiliar que asigne cada vértice a su posición en el montón, y mantener esta estructura actualizada a medida que cambia la cola Q prioritaria . Con un árbol de búsqueda binaria de equilibrio automático o un montón binario, el algoritmo requiere

$${\ displaystyle \ Theta ((| E | + | V |) \ log | V |)}

tiempo en el peor de los casos (donde $${\ displaystyle \ log} denota el logaritmo binario $${\ displaystyle \ log _ {2}}); para gráficos conectados, este límite de tiempo se puede simplificar a$${\ displaystyle \ Theta (| E | \ log | V |)}. El montón de Fibonacci mejora esto a

$${\ displaystyle O (| E | + | V | \ log | V |).}

Cuando se usan montones binarios, la complejidad promedio del tiempo del caso es menor que el peor de los casos: suponiendo que los costos de borde se extraigan independientemente de una distribución de probabilidad común , el número esperado de operaciones de tecla de disminución está limitado por$${\ displaystyle O (| V | \ log (| E | / | V |))}, dando un tiempo total de ejecución de ^{[5] : 199–200}

$${\ displaystyle O \ left (| E | + | V | \ log {\ frac {| E |} {| V |}} \ log | V | \ right).}

Optimizaciones prácticas y gráficos infinitos [ editar ]

En presentaciones comunes del algoritmo de Dijkstra, inicialmente todos los nodos se ingresan en la cola de prioridad. Sin embargo, esto no es necesario: el algoritmo puede comenzar con una cola prioritaria que contiene solo un elemento e insertar nuevos elementos a medida que se descubren (en lugar de hacer una tecla de disminución, verifique si la clave está en la cola; si es es decir, disminuya su clave, de lo contrario insértela). ^[5] : 198 Esta variante tiene los mismos límites de peor caso que la variante común, pero mantiene una cola de prioridad más pequeña en la práctica, acelerando las operaciones de la cola.^[7]

Además, al no insertar todos los nodos en un gráfico, es posible extender el algoritmo para encontrar la ruta más corta desde una sola fuente al más cercano de un conjunto de nodos de destino en gráficos infinitos o aquellos demasiado grandes para representarlos en la memoria. El algoritmo resultante se llama búsqueda de costo uniforme (UCS) en la literatura de inteligencia artificial ^{[7] [15] [16]} y se puede expresar en pseudocódigo como

 procedimiento  UniformCostSearch (Gráfico, inicio, objetivo)
  nodo ← inicio
  costo ← 0
  frontera ← cola prioritaria que contiene solo nodo
  ← conjunto vacío explorado
  hacer 
    si la frontera está vacía
       regresar falla de
    nodo ← frontier.pop ()
    si el nodo es el objetivo de
       retorno solución de
    explored.add (nodo)
    para cada uno de los vecinos del nodo n
       si n no está explorado
          frontier.add (n)

La complejidad de este algoritmo se puede expresar de una manera alternativa para gráficos muy grandes: cuando C ^* es la longitud de la ruta más corta desde el nodo de inicio a cualquier nodo que satisfaga el predicado "objetivo", cada borde tiene un costo de al menos ε , y el número de vecinos por nodo está delimitada por b , entonces el tiempo del peor caso y el espacio del algoritmo de complejidad están ambos en O ( b ^{1 + ⌊ C * / varepsilon ⌋} ) . ^[15]

Las optimizaciones adicionales del algoritmo de Dijkstra para el caso de un solo objetivo incluyen variantes bidireccionales , variantes dirigidas a objetivos como el algoritmo A * (ver § Problemas y algoritmos relacionados ), poda gráfica para determinar qué nodos pueden formar el segmento medio de las rutas más cortas (enrutamiento basado en REACH), y descomposiciones jerárquicos del gráfico de entrada que reducen s - t enrutamiento a la conexión de s y t a sus respectivos " nodos de tránsito ", seguido de cálculo de ruta más corta entre estos nodos de tránsito utilizando un "autopista".^[17] Las combinaciones de tales técnicas pueden ser necesarias para un rendimiento práctico óptimo en problemas específicos. ^[18]

Variantes especializadas [ editar ]

Cuando los pesos de arco son enteros pequeños (delimitados por un parámetro C ), se puede usar una cola de prioridad monótona para acelerar el algoritmo de Dijkstra. El primer algoritmo de este tipo fue el algoritmo de Dial , que utilizaba una cola de depósito para obtener un tiempo de ejecución$${\ displaystyle O (| E | + \ operatorname {diam} (G))}eso depende del diámetro ponderado de un gráfico con pesos de borde entero ( Dial 1969 ). El uso de un árbol de Van Emde Boas como la cola prioritaria trae la complejidad a$${\ displaystyle O (| E | \ log \ log C)}( Ahuja et al. 1990 ). Otra implementación interesante basada en una combinación de un nuevo montón de radix y el conocido montón de Fibonacci se ejecuta a tiempo$${\ displaystyle O (| E | + | V | {\ sqrt {\ log C}})}( Ahuja et al. 1990 ). Finalmente, los mejores algoritmos en este caso especial son los siguientes. El algoritmo dado por ( Thorup 2000 ) se ejecuta en$${\ displaystyle O (| E | \ log \ log | V |)}tiempo y el algoritmo dado por ( Raman 1997 ) se ejecuta en$${\ displaystyle O (| E | + | V | \ min \ {(\ log | V |) ^ {1/3 + \ varepsilon}, (\ log C) ^ {1/4 + \ varepsilon} \}) } hora.

Además, para gráficos acíclicos dirigidos , es posible encontrar rutas más cortas desde un vértice inicial dado en lineal$${\ displaystyle O (| E | + | V |)}tiempo, procesando los vértices en un orden topológico y calculando la longitud del camino para cada vértice como la longitud mínima obtenida a través de cualquiera de sus bordes entrantes. ^[19] [20]

En el caso especial de pesos enteros y gráficos conectados no dirigidos, el algoritmo de Dijkstra se puede contrarrestar completamente con un lineal $${\ displaystyle O (| E |)}algoritmo de complejidad, dado por ( Thorup 1999 ).

Problemas y algoritmos relacionados [ editar ]

La funcionalidad del algoritmo original de Dijkstra se puede ampliar con una variedad de modificaciones. Por ejemplo, a veces es deseable presentar soluciones que sean menos que matemáticamente óptimas. Para obtener una lista clasificada de soluciones menos que óptimas, primero se calcula la solución óptima. Un borde simple que aparece en la solución óptima se elimina del gráfico y se calcula la solución óptima para este nuevo gráfico. Cada borde de la solución original se suprime a su vez y se calcula una nueva ruta más corta. Las soluciones secundarias se clasifican y presentan después de la primera solución óptima.

El algoritmo de Dijkstra suele ser el principio de funcionamiento detrás de los protocolos de enrutamiento de estado de enlace , siendo OSPF e IS-IS los más comunes.

A diferencia de algoritmo de Dijkstra, el algoritmo Bellman-Ford se puede utilizar en gráficos con pesos de las aristas negativas, siempre que el gráfico no contiene ningún ciclo negativo accesible desde el vértice fuente s . La presencia de tales ciclos significa que no hay una ruta más corta, ya que el peso total disminuye cada vez que se atraviesa el ciclo. (Esta afirmación supone que un "camino" puede repetir vértices. En la teoría de grafos normalmente no está permitido. En la informática teórica, a menudo se permite). Es posible adaptar el algoritmo de Dijkstra para manejar bordes de peso negativos combinándolo con el algoritmo de Bellman-Ford (para eliminar bordes negativos y detectar ciclos negativos), dicho algoritmo se llamaEl algoritmo de Johnson .

El algoritmo A * es una generalización del algoritmo de Dijkstra que reduce el tamaño del subgráfico que debe explorarse, si hay información adicional disponible que proporcione un límite inferior en la "distancia" al objetivo. Este enfoque se puede ver desde la perspectiva de la programación lineal : hay un programa lineal natural para calcular las rutas más cortas , y las soluciones a su programa lineal dual son factibles si y solo si forman una heurística consistente (en términos generales, ya que las convenciones de signos difieren de un lugar a otro en la literatura). Esta factible heurística dual / consistente define un costo reducido no negativoy A * está ejecutando esencialmente el algoritmo de Dijkstra con estos costos reducidos. Si el dual satisface la condición más débil de admisibilidad , entonces A * es más parecido al algoritmo de Bellman-Ford.

El proceso que subyace en el algoritmo de Dijkstra es similar al proceso codicioso utilizado en el algoritmo de Prim . El propósito de Prim es encontrar un árbol de expansión mínimo que conecte todos los nodos en el gráfico; Dijkstra se preocupa solo por dos nodos. Prim no evalúa el peso total de la ruta desde el nodo inicial, solo los bordes individuales.

La búsqueda de amplitud se puede ver como un caso especial del algoritmo de Dijkstra en gráficos no ponderados, donde la cola de prioridad degenera en una cola FIFO.

El método de marcha rápida puede verse como una versión continua del algoritmo de Dijkstra que calcula la distancia geodésica en una malla triangular.

Perspectiva de programación dinámica [ editar ]

Desde el punto de vista de la programación dinámica , el algoritmo de Dijkstra es un esquema de aproximación sucesivo que resuelve la ecuación funcional de programación dinámica para el problema del camino más corto mediante el método Reaching . ^{[21] [22] [23]}

De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, ^{[24] a} saber

Problema 2. Encuentre la ruta de longitud total mínima entre dos nodos dados$${\ displaystyle P} y $${\ displaystyle Q}.

Usamos el hecho de que, si $${\ displaystyle R} es un nodo en la ruta mínima desde $${\ displaystyle P} a $${\ displaystyle Q}, el conocimiento de este último implica el conocimiento del camino mínimo desde $${\ displaystyle P} a $${\ displaystyle R}.

es una paráfrasis del famoso Principio de Optimidad de Bellman en el contexto del problema del camino más corto.