No hay un bucle negativo, ¿cuál es el motivo del bucle de salida del algoritmo de ruta más corta (algoritmo Floyd-Warshall, Bellman-Ford, implementación de MATLAB)?
La idea del algoritmo de Dijkstra
La idea del algoritmo de Dijkstra es: Supongamos que G = (V, E) es un gráfico dirigido ponderado (el no dirigido puede ser convertido en un gráfico dirigido bidireccional), divida el conjunto de vértices V en el gráfico en dos grupos. El primer grupo es el conjunto de vértices para los cuales se ha encontrado el camino más corto (representado por S. Sólo hay un punto fuente en el S inicial. Cada vez que se encuentra un camino más corto posteriormente, se agrega al conjunto S hasta que todos Los vértices se agregan a S y el algoritmo finaliza. Durante el proceso de empalme, siempre mantenga la longitud del camino más corto desde el punto de origen V hasta cada vértice en S que no sea mayor que la longitud del camino más corto desde el punto de origen V hasta cualquier vértice en U. Además, cada vértice corresponde a una distancia, y la distancia entre los vértices en S es La longitud del camino más corto desde V hasta este vértice, la distancia desde el vértice en U es la longitud del camino más corto actual desde V hasta este vértice, incluyendo solo los vértices en S como vértices intermedios
Los pasos específicos del algoritmo de Dijkstra
(1) Inicialmente, s solo contiene el punto fuente, es decir, s = {v} , y la distancia dist[v] de v es 0. U contiene otros vértices excepto V, y la distancia entre vértices en U es dis[ u], es el peso de la arista (si V y U tienen una arista) o ∞ (si U no es un borde vecino de V, entonces no hay borde < V, u gt)(2) Desde U. Seleccione un vértice K con la distancia más pequeña v(dist[k]) y agregue K a S (la distancia seleccionada es la longitud del camino más corto de V a K)
(3) Tome K como la nueva consideración El punto medio de U, modifique la distancia de cada vértice en. U; si la distancia desde el punto de origen V al vértice u (u∈ U) (pasando por el vértice K) es más corta que la distancia original (sin pasar por el vértice K), modifique la distancia del valor de distancia del vértice U y agregue el distancia del valor de distancia modificado al vértice K más el peso del borde (es decir, si dist [k] w [k, u]
(4) Repita los pasos (2) y (3), hasta que todos los vértices están incluidos en S (bucle n-1 veces)
╝①
Implementación del algoritmo de Dijkstra
╔
Implementación directa<. /p>
La forma más sencilla es encontrar el punto con la distancia más corta en cada bucle y luego actualizar sus bordes adyacentes mediante cualquier método. La complejidad del tiempo es obviamente O (n?)
Para. Complejidad del espacio: si solo necesita la distancia, solo necesita guardar la distancia en el espacio adicional de n (si la distancia es menor que la distancia actual, puede hacer una comparación numérica o un tratamiento especial para la misma distancia). se requiere una ruta, se necesita otro espacio V para guardar el nodo anterior, se requiere un total de * * * 2n espacio
╔
Código Cpp
/**********************************
*Ruta más corta: implementación del algoritmo de Dijkstra
*HDU: 2544 personas
*Blog: www.cnblogs.com/newwy
*Autor: Wang Yong
** ********************************/
# incluir ltiostream gt
#Definir máximo 100
#Definir INF 100000000
Usar espacio de nombres estándar
int dijkstra (int mat[][MAX], int n, int s, int f)
{
int dis[MAX];
int mark[MAX] //Registra el nodo seleccionado.
int i,j,k = 0;
for(I = 0;i ltn;I)//Inicializa todos los nodos, no seleccionas cada nodo.
mark[I]= 0;
for(I = 0;I ltn;I)//Registra el peso de cada nodo hasta el nodo inicial como la distancia actual.
{
dis[I]= mat[s][I];
//ruta[I]= s;
}
mark[s]= 1; //Seleccionar // iniciar nodo
//path[s]= 0;
dis[s] = 0; // Establece la distancia del nodo inicial en 0.
int min//Establece la distancia más corta.
for(I = 1; i ltn; i )
{
min = INF
for(j = 0; j ltn; j )
{
if(mark[j]= = 0 amp; ampdis[j] lt;Min)//Entre los nodos no seleccionados, la distancia de selección es la nodo más corto.
{
min = dis[j]
k = j
}
}
mark[k]= 1; // Marcar como seleccionado
for(j = 0; j ltn; j )
{
if(mark[j]= = 0 amp; amp(dis[j] gt; (dis[k] mat[k][j])//Modifica la distancia más corta de los nodos restantes.
{
dis[j]= dis[k] mat[k][j];
}
}
}
return dis[f];
}
int mat[MAX][MAX];
int main()
{
int n, m;
mientras(scanf("d d ", ampn amp; m))
{
int a, b, dis
if (n == 0 || m == 0)
romper;
int i, j ;
for(I = 0;i ltn;i)
for(j = 0;j ltn;j)
mat[I][j ]= INF;
for(I = 0;iltm;i)
{
scanf("d d d", amp one, ampb amp; dis)
- a, -b;
if(dis lt; mat[a][b]| | dis lt; mat[b][a])
mat[a][b]= mat[b]= dis;
}
int ans = dijkstra(mat, n, 0, n-1); /p>
}
int ans = dijkstra(mat, n, 0, n-1);
;}
}
╝⑤
╔
Implementación del montón binario
Usar un montón binario para guardar la distancia de los puntos no expandidos y mantener su valor mínimo. Se actualiza cuando se accede a cada borde. La complejidad del tiempo puede convertirse en O ((V E) logV). El número de aristas es mucho menor que el cuadrado del número de puntos.
Pero cuando E = O (V2) (a veces indica que el número de aristas no está limitado), la optimización del montón binario será más lenta. Porque la complejidad en este momento es O (V V * 2logV), que es más complicada que O (n?).
Además, se debe utilizar la lista de adyacencia para guardar los bordes de modo que la complejidad total de los bordes extendidos sea O (E); de lo contrario, la complejidad no se reducirá.
Complejidad del espacio: este algoritmo requiere un montón binario y su puntero inverso, y también necesita guardar la distancia, por lo que el espacio utilizado es 3V. Si la ruta de guardado es 4V.
Idea específica: primero inserte todos los puntos en el montón, asigne el valor al valor máximo (maxint / maxlongint), asigne el valor de origen a 0, actualícelo mediante tecnología relax y configúrelo en expansión.
╝②
╔
código c
int GraphDijk(gráfico de estructura *g, int root, int *parent, int * distancia)
{
//Coloque todos los puntos excepto el nodo raíz en el montón y establezca todas las claves en infinito.
//Atraviesa los bordes enviados por el nodo raíz, establece su ruta más corta con el peso correspondiente y mantiene el atributo de montón.
// RemoveTop, este nodo ha adoptado el camino más corto. Si es infinito, el algoritmo terminará.
// De lo contrario, establezca su estado en marcado y configúrelo en el nodo raíz.
//Retorno de bucle
parent[root]= root;
int reflexión[g->v];
int montón _ real[g- gt; v-1];
for (int i=0, j = 0; i ltg- gt; v-1) {
if (i == raíz) {
Distancia[I] = 0;
} En caso contrario {
Distancia[i] = infinito;
montón _ real[j]= I;
Reflexión[I]= j
}
}
Borde estructural* e; ;
struct list _ t * iter
int * heap = heap _ real-1
int base = 0 /* euqal a distancia [root] ] */
int tamaño = g- gt;
int longitud
hacer {
ITER = lista; _ next(&(g->vertex root)->link);
for(iter = list_next(iter)) {
e = list_entry(iter, struct Edge, link );
Longitud = base e- gt; peso;
if (longitud lt distancia [e->; a]) {
HeapDecreaseKey(heap, tamaño,
distancia, reflexión,
reflexión[e->;to], longitud);
padre[e-gt;to ]= raíz;
}
}
root = HeapRemoveTop(montón, tamaño, distancia, reflexión
base = distancia [raíz]);
if (distancia [raíz] == infinito){
/*Los nodos restantes en el montón son inaccesibles*/
Devuelve g- gt ; V - (tamaño 1); /*Devuelve el número de nodos de rama fuertemente conectados*/
}
} while (tamaño);
/* Finaliza con éxito el algoritmo m */
Devuelve g- gt; cinco;
}
╝④
Dame otra experiencia
} p>
╔
código c
/*El camino más corto de agua desnuda, Dijstra practica la optimización del montón binario~
Prim usa optimización del montón binario, depura durante más de ocho horas y golpea varias veces, pero aún sin éxito.
Pero afortunadamente estoy familiarizado con el funcionamiento de la cola de prioridad.
Hoy, más de diez días después, volví a pensar en esto y finalmente saqué Dijstra optimizado para el montón. Es bastante simple una vez que lo entiendes.
Algunos métodos de escritura no son óptimos, como reducir los elementos de intercambio en la implementación del montón. Pero con este AC Dijkstra escrito por mí mismo, puedo compararlo con Debug al escribir Prim/Dijkstra optimizado para el montón binario y otros temas de colas prioritarias en el futuro.
2011-07-24 23:00
*/
# incluir ltstdio.h gt
#Definición MAXN 1200 p>
#Define MAXM 1200000
#Define INF 19930317
Nodo de estructura
{
int d, v , p ;
} montón[MAXN];
int pos[MAXN], HL;
int e[MAXM], costo[MAXM], siguiente [MAXM ], g[MAXN], tamaño
int m, n, s, t;
inserción vacía(int u, int v, int w)
{
e[tamaño]= v;
siguiente[tamaño]= g[u];
Costo[tamaño]= w;
g[u] = tamaño;
}
intercambio vacío(int a, int b)
{
montón [0]= montón[a];
montón[a]= montón[b];
montón[b]= montón[0];
montón. v]= a;
Montón. v] = b;
}
Apilamiento no válido()
{
int I = 2;
while(i lt= hl)
{
if ((i lthl) y amp amp(heap[i 1].d ltheap[i].d))
i;
if(montón[i].d ltheap[I gt; gt1].d)
{
intercambiar (i ,i gt gt1);
i lt lt= 1;
}
Otro
Descanso;
}
}
Reducción no válida (int i)
{
mientras ((i! = 1); amp (montón [i].d ltheap[I gt; gt1].d))
{
intercambio(i,i gt gt1);
i gt gt = 1;
}
}
void relax(int u, int v, int w)
{< / p>
if (w montón[pos[u]]. d lt montón, montón. d)
{
Montón, montón. p = u;
Montón, montón. d = w montón[pos[u]].
d;
reducir(posición[v]);
}
}
void delete_min()
{
intercambio(1, HL);
HL-;
montón fy();
}
inicialización nula()
{
int u, v, w, I
scanf("dd ", ampm amp; n);
for(I = 1;ilt= m;i)
{
scanf("ddd", ampu amp;v, ampw
Insertar (u, v, w);
Insertar (v, u, w
}
s = 1 ;
t = n;
}
int dijkstra()
{
int u, p , I ;
for(I = 1; i lt= n; i)
{
Montón[i]. v = pos[I]=I;
Montón[i]. d = INF
}
montón. p = s;
Montón. d = 0;
intercambio(1, s);
HL = n;
Blanco (hl)
{
u = montón[1]. Cinco;
eliminar _ min();
p = g[u];
mientras (p)
{
if(pos[e[p]] lt; = hl)
relax(u, e[p], costo[p]); siguiente[p];
}
}
}
int main()
{
init();
Dijkstra();
printf("d\n ", montón[pos[t]].d);
Devuelve 0;
}
╝③
╔
Implementación del reactor de Fibonacci
Del mismo modo, El montón de Fibonacci puede reducir la complejidad a O (E VlogV), pero es más problemático de implementar. Por lo tanto, no figuran aquí.