Cómo determinar el camino más corto entre dos puntos utilizando matlab de ponderación de gráficos no dirigidos conocidos

Cómo determinar la ruta más corta de dos puntos en matlab con ponderación de gráfico no dirigida conocida

función [L, Z]=dijkstra(W, S, T)

Utilice el algoritmo de Dijkstra para encontrar el camino más corto

Algoritmo

1. Especifique un valor de distancia inicial L(I) desde el punto S para cada punto I. El valor en el punto inicial S es cero, es decir L (S) = 0, el valor de otros puntos es Inf

2. Todos los puntos están marcados como no visitados. Establezca el punto inicial S como el punto actual C.

3. Para el punto actual C, considere todos sus puntos adyacentes no visitados J y actualice el valor de distancia de J a

L(J)=min(L(J), L( C) W(C, J))

4. Marque el punto actual C como punto visitado. La distancia L(C) desde el punto visitado C es la distancia más corta desde el punto S a C, y los puntos visitados ya no se verificarán en el futuro. Obtuve el punto

5. Si todos los puntos son puntos visitados, complete. De lo contrario, use el punto con el valor de distancia mínimo entre los puntos no visitados. siguiente punto actual C, vaya a

N=length(W(:,1)); número de vértices

W(find(W==0))=inf;

L=Inf*ones (1, N);

L(S)=0; a L se le asigna un valor inicial, que es 0 en el punto S e Inf en los demás puntos.

C=S; El punto actual es el punto de partida S

Q=1:N Conjunto de vértices no visitados

Z=S*ones(1, N);

Z(S)=0 ; Asigne un valor inicial a Z. Dado que el punto inicial S no tiene un punto principal, cambie el valor Z del punto S a 0

para K=1: N actualiza el bucle L y Z