Cómo implementar el algoritmo de Dijkstra usando programación matlab

El algoritmo de Dijkstra es un algoritmo de búsqueda para encontrar el camino más corto, propuesto por científicos holandeses.

Descripción del algoritmo: Reteniendo para cada nodo el camino más corto de s a e encontrado hasta el momento. Para registrar la mejor trayectoria, registre el predecesor de cada nodo en la ruta y encuentre la trayectoria más corta mediante el método de retroceso.

Después de buscar algunas versiones de los métodos de implementación de Matlab en Internet, siento que hay algunos problemas. Después de la modificación se obtuvieron mejores resultados.

[cpp] ver copia simple

función [ruta de distancia] = Dijk( W,st,e )

%DIJK El resumen de esta función va aquí

% W peso matriz st punto inicial de búsqueda e punto final de búsqueda

n=longitud(W);% número de nodos

D = W(st ,: );

visit= ones(1:n); visit(st)=0;

parent = zeros(1,n);% registra el nodo anterior de cada uno. nodo

ruta =[];

for i=1:n-1

temp = []; Desde el punto de partida, busque el siguiente punto con la distancia más corta y la trayectoria original no se repetirá cada vez. Configure la visita para determinar si se visita el nodo

para j=1:n

.

si visita(j)

temp =[temp D(j)];

else

temp =[temp inf]

fin

fin

[valor,índice] = min(temperatura

visita(índice) = 0

<); p>% de actualización si pasa el nodo índice. Si la longitud de la ruta desde el punto inicial a cada nodo es menor, actualice y registre el nodo predecesor para facilitar el seguimiento posterior

para k=1:n

if D(k) >D(índice)+W(índice,k)

D(k) = D(índice)+W(índice,k

);

padre(k) = índice

final

final

final

distancia = D(e);% más corto distancia

% retroceso Método para encontrar la ruta de búsqueda desde la cola hacia adelante

t = e

mientras t~=st && t>0

ruta =[t,ruta];

p=parent(t);t=p

fin

ruta =[st, ruta];% ruta más corta

fin

Prueba:

Caso de prueba 1

[cpp] ver copia simple

W=[0 50 inf 40 25 10

50 0 15 20 inf 25

inf 15 0 10 20 inf

40 20 10 0 10 25

25 inf 20 10 0 55

10 25 inf 25 55 0];

[cpp] ver copia simple

[ cpp] ver copia simple

[distancia,ruta]=Dijk(W,1,4

distancia

distancia =

);

35

> > ruta

ruta =

1 6 4

La ruta de distancia más corta desde el nodo 1 al nodo 4 es 1-->6-->4, la distancia más corta es 35