6.3.1 Algoritmos de recorrido y búsqueda El camino más corto

6.3.1 Algoritmos de recorrido y búsqueda El camino más corto/ Codigo C#

También conocido como los problemas de los caminos cortos entre dos nodos.

Algoritmo de Floyd-Warshall

Algoritmo de Warshall de Floyd

• El algoritmo de Floyd se usa para encontrar la ruta más corta entre cada par de vértices de una gráfica. El algoritmo funciona tanto para gráficos dirigidos como no dirigidos.
• La gráfica puede contener bordes negativos, pero no puede contener ningún ciclo negativo.
• Requiere gráficos ponderados.
• Calcula la matriz de distancia de un gráfico ponderado con 'n' vértices a través de una serie de matrices 'nxn'.
  
  D ^ 0, D ^ 1, D ^ 2. . . . . . . . . . . D ^ k-1,. . . . , D ^ n
• En cada matriz, Dk es la distancia más corta y 'Dij' debe calcularse entre vértice (Vi y Vj).
• En particular, la serie comienza con D0 sin vértice intermedio. Esto significa que D0 es una matriz en la que (Vi y Vj) que es (la fila i y la columna J) contiene los pesos están dados por bordes directos.
• En la matriz D1, se proporciona la distancia más corta que atraviesa un vértice intermedio con una longitud de trayectoria máxima de 2 bordes.
• Continuando de esta manera, calcularemos Dn, que contiene las longitudes de la ruta más corta entre todas las rutas que pueden usar todos los vértices 'n' como intermedios.

Ejemplo basado en Floyd's Warshall

Desde el gráfico, solo tiene que calcular el peso para mover un nodo a otro nodo, como si desea ir al nodo 1 - -> nodo 2, el costo es -> 8. Para moverse al nodo 3 al nodo 1, puede ver que no hay una ruta directa disponible para el nodo 3 - - nodo 1, por lo que debe tomar el nodo intermedio. En nuestro caso, el nodo 2 se convertirá en nuestro nodo intermedio. El costo de mover el nodo 3 - -> nodo 1 es - -> 3 (1 + 2) -> {costo de mover el nodo3 -> nodo2 + nodo2 nodo1}. 

Primero, calculamos el -> D0

D1 1 es un nodo intermedio.

D2 2 es un nodo intermedio.

D3 3 es un nodo intermedio.

El último D3 es tu matriz de distancia, que te da la distancia más corta entre los nodos. 

El último D3 es tu matriz de distancia, que te da la distancia más corta entre los nodos.

Algoritmo de la

entrada del juego de guerra de Floyd : la matriz ponderada wt [1 ... n, 1 ... .n,] para el gráfico dado.

Salida

La matriz de distancia D contiene las rutas más cortas.

1. D0 -> W // Inicializar la matriz D a w []
2. P - -> 0 // Inicializar la matriz P a [0]
3. para k -> 1 a n do
4. para i -> 1 a n do
5. para j -> 1 a n
6. si (Dk-1 [i, j]> Dk-1 [i, k] + Dk-1 [k, j])
7. entonces Dk [i, j] <- Dk-1 [i, k] + Dk-1 [k, j]
8. P [i, j] <- k;
9. otra cosa Dk [i, j] <- Dk-1 [i, j]

Análisis del algoritmo

D [i, j] min {D [I, j], D [I, k] + D [K, j]}

Ahora, esta operación está en tres bucles anidados y, por lo tanto, se puede escribir, como se muestra a continuación .

C (n) =
C (n) =
C (n) =: - [= ½ n2]
A partir de eso,
C (n) = [= 1/3 n3]

Por lo tanto, la complejidad del tiempo del algoritmo de Floyd es - grande O (n ^ 3).

Implementación del algoritmo de Floyd en C #

1. 
   using System;  
2. using System.Collections.Generic;  
3. using System.Linq;  
4. using System.Text;  
5.   
6. namespace Floyds_Warshall_Algorithm {  
7.     class Program {  
8.   
9.         public  
10.         const int INF = 10000;  
11.   
12. private static void disp(int[, ]distance, int verticesCount){  
13. Console.WriteLine("Distance Matrix for Shortest Distance between the nodes");  
14.             Console.Write("\n");  
15.   
16.             for (int i = 0; i < verticesCount; ++i) {  
17.                 for (int j = 0; j < verticesCount; ++j) {  
18.                     // IF THE DISTANCE TO THE NODE IS NOT DIRECTED THAN THE COST IN iNIFINITY  
19.   
20.                     if (distance[i, j] == INF)  
21.                         Console.Write("INF".PadLeft(7));  
22.                     else  
23.                         Console.Write(distance[i, j].ToString().PadLeft(7));  
24.                 }  
25.   
26.                 Console.WriteLine();  
27.             }  
28.         }  
29.   
30.         public static void FloydWarshall(int[, ] graph, int verticesCount) {  
31.             int[, ] distance = new int[verticesCount, verticesCount];  
32.   
33.             for (int i = 0; i < verticesCount; ++i)  
34.                 for (int j = 0; j < verticesCount; ++j)  
35.                     distance[i, j] = graph[i, j];  
36.   
37.             for (int k = 0; k < verticesCount; k++) {  
38.                 for (int i = 0; i < verticesCount; i++) {  
39.                     for (int j = 0; j < verticesCount; j++) {  
40.                         if (distance[i, k] + distance[k, j] < distance[i, j])  
41.                             distance[i, j] = distance[i, k] + distance[k, j];  
42.                     }  
43.                 }  
44.             }  
45.   
46.             disp(distance, verticesCount);  
47.             Console.ReadKey();  
48.   
49.         }  
50.   
51.         static void Main(string[] args) {  
52.             //inital Graph Given = D^0  
53.   
54.             int[, ] graph = {  
55.   
56.                 {  
57.                     0,  
58.                     8,  
59.                     5  
60.                 },  
61.                 {  
62.                     2,  
63.                     0,  
64.                     INF  
65.                 },  
66.                 {  
67.                     INF,  
68.                     1,  
69.                     0  
70.                 },  
71.   
72.             };  
73.   
74.             FloydWarshall(graph, 3);  
75.   
76.         }  
77.   
78.     }  
79.   
80. } // 
81.   
82. if ('this_is' == /an_example/) {  
83.     of_beautifier();  
84. } else {  
85.     var a = b ? (c % d) : e[f];  
86. }  

Input Graph

Gráfico de entrada

Aquí, ha proporcionado un gráfico de entrada, que es un gráfico dirigido y ponderado según el requisito del algoritmo de Floyd. A partir de aquí, se moverá al método Floydwarshall para analizarlo. 

Aquí, comprobará si el nodo de origen y el nodo de destino están conectados o no. Si está conectado, encontrará el camino más corto mínimo de todos los nodos intermedios, pero un paso a la vez. 

Salida

Este es el último gráfico de matriz de distancia, donde puede verlo moverse de cualquier nodo a cualquier nodo y obtendrá el camino más corto mínimo. 

Código C#

Algoritmo Dijkstra:

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

Dado un gráfico y un vértice de origen en el gráfico, encuentre las rutas más cortas desde la fuente a todos los vértices en el gráfico dado.

El algoritmo de Dijkstra es muy similar al algoritmo de Prim para el árbol de expansión mínimo . Al igual que MST de Prim, generamos un SPT (árbol de ruta más corto) con una fuente dada como raíz. Mantenemos dos conjuntos, un conjunto contiene vértices incluidos en el árbol de la ruta más corta, otro conjunto incluye vértices que aún no están incluidos en el árbol de la ruta más corta. En cada paso del algoritmo, encontramos un vértice que está en el otro conjunto (conjunto de aún no incluido) y tiene una distancia mínima de la fuente.

A continuación se muestran los pasos detallados utilizados en el algoritmo de Dijkstra para encontrar la ruta más corta desde un vértice de una sola fuente a todos los otros vértices en el gráfico dado.

Algoritmo
1) Cree un conjunto sptSet (conjunto del árbol de la ruta más corta) que haga un seguimiento de los vértices incluidos en el árbol de la ruta más corta, es decir, cuya distancia mínima desde la fuente se calcula y finaliza. Inicialmente, este conjunto está vacío.                    
2) Asigne un valor de distancia a todos los vértices en el gráfico de entrada. Inicialice todos los valores de distancia como INFINITE. Asigne el valor de la distancia como 0 para el vértice de origen para que se seleccione primero.                    
3) Mientras que sptSet no incluye todos los vertices             
…. a) Elija un vértice u que no esté allí en sptSety tiene valor de distancia mínima.  
... b) Incluir u para sptSet .                    
... c) Actualizar el valor de la distancia de todos los vértices adyacentes de u. Para actualizar los valores de distancia, itera a través de todos los vértices adyacentes. Para cada vértice adyacente v, si la suma del valor de distancia de u (desde la fuente) y el peso del borde uv, es menor que el valor de distancia de v, entonces actualice el valor de distancia de v.

Entendamos con el siguiente ejemplo:

El conjunto sptSet está inicialmente vacío y las distancias asignadas a los vértices son {0, INF, INF, INF, INF, INF, INF, INF} donde INF indica infinito. Ahora elige el vértice con el valor de distancia mínima. El vértice 0 es seleccionado, incluirlo en sptSet . Entonces sptSet se convierte en {0}. Después de incluir 0 en sptSet , actualice los valores de distancia de sus vértices adyacentes. Los vértices adyacentes de 0 son 1 y 7. Los valores de distancia de 1 y 7 se actualizan como 4 y 8. El subgrafo siguiente muestra los vértices y sus valores de distancia, solo se muestran los vértices con valores de distancia finitos. Los vértices incluidos en SPT se muestran en color verde.

Elija el vértice con el valor de la distancia mínima y no incluido en SPT (no en sptSET). El vértice 1 se selecciona y se agrega a sptSet. Entonces sptSet ahora se convierte en {0, 1}. Actualice los valores de distancia de vértices adyacentes de 1. El valor de distancia del vértice 2 se convierte en 12.

Elija el vértice con el valor de la distancia mínima y no incluido en SPT (no en sptSET). Se selecciona vértice 7. Así que sptSet ahora se convierte en {0, 1, 7}. Actualice los valores de distancia de vértices adyacentes de 7. El valor de distancia de los vértices 6 y 8 se convierte en finito (15 y 9 respectivamente).

Elija el vértice con el valor de la distancia mínima y no incluido en SPT (no en sptSET). Se selecciona vértice 6. Así que sptSet ahora se convierte en {0, 1, 7, 6}. Actualice los valores de distancia de vértices adyacentes de 6. El valor de distancia de los vértices 5 y 8 se actualiza.

Repetimos los pasos anteriores hasta que sptSet no incluya todos los vértices de un gráfico dado. Finalmente, obtenemos el siguiente Árbol de ruta más corto (SPT).

¿Cómo implementar el algoritmo anterior?

Usamos una matriz booleana sptSet [] para representar el conjunto de vértices incluidos en SPT. Si un valor sptSet [v] es verdadero, entonces el vértice v se incluye en SPT, de lo contrario no. Array dist [] se utiliza para almacenar valores de distancia más cortos de todos los vértices.