Para un gráfico con n vértices y e aristas, el camino más corto desde un vértice Vi a cualquier otro vértice Vj puede ser el borde (Vi, Vj) entre ellos, también puede ser un camino formado por K vértices intermedios y k+1 aristas (1≤k≤n-2). A continuación se da la idea del algoritmo de Dijkstra para resolver este problema.
Supongamos que el gráfico G se almacena en GA en forma de matriz de adyacencia, donde GA[i, j]=maxint significa que Vi y Vj son irrelevantes, de lo contrario es un peso (un número real mayor que 0). Utilice el conjunto S para almacenar el número terminal del camino más corto. El comienzo S=[Vi] significa solo el punto fuente. Después de eso, cada vez que se encuentre un punto final Vj, se agregará al conjunto como un vértice intermedio recién considerado. Deje que la matriz dist[1...n] se utilice para almacenar la ruta más corta obtenida actualmente. Si existe una relación entre Vi y Vj al principio, dist [j] es igual al peso; de lo contrario, es igual a maxint. En el futuro, dist[j] puede volverse cada vez más pequeño a medida que se consideren cada vez más vértices intermedios considerados recientemente. Establezca la ruta de la matriz [1...n] correspondiente a dist para almacenar los bordes de la ruta más corta actual. Inicialmente, es el borde de Vi a Vj. Si no hay borde, está vacío.
Al ejecutar, busque el elemento con el valor más pequeño (se supone que es dist[m]) de los elementos de la matriz dist correspondientes a los vértices distintos de S. Esta es la longitud de ruta más corta desde el punto de origen Vi al destino Vm. La secuencia de vértices o aristas correspondientes al camino [m] es el camino más corto. Luego, Vm se fusiona con el conjunto S, y luego Vm se toma como el vértice intermedio recién considerado. Para cada vértice Vj excepto S, compare el tamaño de dist[j] de dist[m]+GA[m, j]. Si el primero es más pequeño, significa que se puede obtener una mejor solución agregando nuevos vértices intermedios, es decir, se puede obtener un camino más corto [j], así que úselo en lugar de dist[j], y también use Vj o edge . Repita el proceso anterior n-2 veces para obtener la longitud de la ruta más larga desde el punto de origen a los otros puntos finales en la matriz dist y guarde la ruta más larga correspondiente en la matriz de ruta correspondiente.
El marco específico del algoritmo de Dijkstra se proporciona a continuación (Nota: para facilitar la implementación, se utiliza una matriz unidimensional S [1...n] para guardar el conjunto de puntos finales de la ruta más corta, es decir, si s[j] =0 significa que el vértice Vj no está en el conjunto, por el contrario, s[j]=1 significa que el vértice Vj está en el conjunto).
Programa Dijkstra(GA, dist, path, I);
{Indica encontrar el camino más corto desde Vi a otros vértices en el gráfico G, donde GA es la matriz de adyacencia del gráfico G , dist y path son parámetros variables,
el tipo básico de ruta está establecido}
Inicio
Para j:=1 an, inicie {inicialización }
Si j & lt& gtI entonces s[j]:= 0 Si no s[j]:= 1;
dist[j]:=GA[i,j];
si dist[j]< maxint entonces ruta[j]:=[I]+[j]Else ruta[j]:=[];
Fin;
Fin p>
Para k:=1 a n-2 Hacer
Iniciar
w:= maxint;
Para j: =1 a n Haga {Encontrar el k-ésimo punto final Vm}
Si (s[j]=0) y (dist[j]<w) entonces inicie m: = j;w:= dist[j];End;
Si m & lt& gtI entonces s[m]:=1 else sale;
{Si la condición es verdadera, agregue la máquina virtual a S.
De lo contrario, salga del ciclo, porque la longitud de ruta más corta de los puntos finales restantes es maxint, por lo que no es necesario calcularla nuevamente.
Para j:=1 to n Haga {realizar las modificaciones necesarias para mejorar los elementos con s[j]=0}
Si (s[j]=0) y (dist[ m]+GA[m,j]<dist[j])
Luego comienza Dist[j]:=dist[m]+GA[m,j]; [m]+[j]; Fin;
Fin;
Fin;
(1) La ruta más corta de un vértice a otros vértices.
Para un gráfico con n vértices y e aristas, el camino más corto desde un vértice vi a cualquier otro vértice vj pueden ser las aristas (vi, vj) entre ellos, o puede ser K El camino formado por el punto intermedio y k+1 aristas (1≤k≤n-2).
Analicemos primero el pensamiento algorítmico de Dijkstra.
Supongamos que el gráfico G se almacena en GA en forma de matriz de adyacencia, donde GA[I, j]=maxint significa que vi y vj son irrelevantes, de lo contrario es un peso (un número real mayor que 0). Deje que el conjunto S se utilice para almacenar y guardar el número de terminal de la ruta más corta. Al principio, S = [vi] significa solo el punto de origen. En el futuro, cada vez que se encuentre un vj terminal, se agregará al conjunto como un vértice intermedio recién considerado. Deje que la matriz dist[1...n] se utilice para almacenar la ruta más corta obtenida actualmente. Si existe una relación entre vi y vj al principio, dist [j] es igual al peso; de lo contrario, es igual a maxint. En el futuro, dist[j] puede volverse cada vez más pequeño a medida que se consideren cada vez más vértices intermedios considerados recientemente. Establezca la ruta de la matriz [1...n] correspondiente a dist para almacenar los bordes de la ruta más corta actual. Inicialmente, el borde de vi a vj estará vacío si no hay ningún borde.
Al ejecutar, busque el elemento con el valor más pequeño (se supone que es dist[m]) de los elementos de la matriz dist correspondientes a los vértices distintos de S. Esta es la longitud de ruta más corta desde el punto de origen vi a la vm de destino. La secuencia de vértices o aristas correspondientes a la ruta [m] es la ruta más corta. Luego, vm se fusiona con el conjunto S y luego se toma vm como el vértice intermedio recién considerado. Para cada vértice vj excepto S, compare los tamaños de dist[m]+GA[i, j] y dist[j]. Si el primero es más pequeño, significa que se puede obtener una mejor solución agregando nuevos vértices intermedios, es decir, se puede obtener una ruta más corta [j], así que úselo en lugar de dist [j], y también use vj o edge . Repita el proceso anterior n-2 veces para obtener la longitud de ruta más corta desde el punto de origen a los otros puntos finales en la matriz dist y guarde la ruta más corta correspondiente en la matriz de ruta correspondiente.
Para facilitar la implementación, la matriz unidimensional S [1...n] reemplaza el conjunto S y se utiliza para guardar el conjunto de puntos finales de la ruta más corta, es decir, si s[j ]=0 significa que el vértice vj no está en el conjunto. Por el contrario, s[j] significa que el vértice vj ya está en el conjunto).
programa dijkstra (GA, ruta dist, I)
Inicio
Para j:= 1 an n iniciar
Si j & lt& gtI Entonces s[j]:= 0; {j no está en el conjunto} else s[j]:= 1; {j está en el conjunto}; GA[I , J];
IF dist[j]& lt; Maxint {maxint es un número hipotéticamente lo suficientemente grande}
Entonces ruta [j]:=[I]+ [ j]
Else path[j]:=[];
Fin;
Para k:= 1 a n-1 comience w:= maxint ;m:= I;
Para j:= 1 an do{encontrar el k-ésimo punto final Vm}
if (s[j]=0) y (dist [j ]& lt; w) luego comienza m:= j; w:= dist[j]
si m & lt& gtI entonces s[m]:=1 else sale; la condición es verdadera, agregue Vm a S; de lo contrario, salga del ciclo, porque
La longitud de ruta más corta de los puntos finales restantes es maxint, por lo que no es necesario calcularla nuevamente.
Para j:=1 an {realizar las modificaciones necesarias para mejorar los elementos con s[j]=0}
if (s[j]=0)y (dist[ m]+GA[m,j]<dist[j])
Comencemos
dist[j]:=dist[m]+GA[ m, j] ;
ruta[j]:= ruta[m]+[j];
Fin
Fin
Fin;
Con la idea de configurar:
Para k:=1 a n-1 haz
Iniciar
WM:= max; j:= 0;
Para i:=1 to n do
Si no (i in s) y (dist[I]<wm) Entonces inicie j: = I; WM:= dist[I]; fin;
s:= s+[j]; Si no (i en s) y (dist[j]+costo[j,I]<dist[I]entonces
comienza dist[I]:= dist[j] +costo[j, I];ruta[I]:= ruta[j]+char(48+I);fin;
fin;