Algorytm Djikstry

0

Witam, mam problem z algorytmem Djikstry w Matlabie.

user image

Mam problem z dodaniem 1. ścieżki w grafie (zaznaczonej na czerwono) w Matlabie. Byłby ktoś w stanie pomóc?

Pozdrawiam.

To jest kod na graf bez tej czerwonej ścieżki.

clear 
clc
 W=[0 15 inf inf 9 inf,
 inf 0 35 3 inf inf,
 inf 16 0 6 inf 21,
 inf inf inf 0 2 7,
 inf 4 inf 2 0 inf,
 inf inf 5 inf inf 0];
s=6;
t=1;
dist=[];
final=[];
pred=[];
n=size(W,1);
for v = 1: n
    dist(v)=inf;
    final(v)=false;
    pred(v)=-1;
end
dist(s)=0;
final(s)=true;
path=true;
recent=s;
while final(t)==false;
    for v=1:n
        if (W(recent,v)<inf) && (~final(v))
            newlabel=dist(recent)+W(recent,v);
            if newlabel< dist(v)
                dist(v)=newlabel;
                pred(v)=recent;
            end
        end
    end
    temp=inf;
    for u=1:n
        if (~final(u) && dist(u) <temp)
            y=u;
            temp=dist(u);
        end
    end
    if temp <inf
        final(y)=true;
        recent=y;
    else
        path=false;
        final(t)=true;
    end
end

if (path)
    odleglosc=dist(t);
    poprzednik=t;
    h=2;
    g(1)=poprzednik;
    while (true)
        g(h)=pred(poprzednik);
        if (pred(poprzednik)==s)
            break;
        end
        d=poprzednik;
        poprzednik=pred(d);
        h=h+1;
    end
    droga=g(end:-1:1);
    droga
    odleglosc
else 
    'Nie znaleziono drogi'
end
0

Musisz jedno z tych inf w tablicy W zamienić na tą twoją 1. Nie wiem które bo na obrazku nie ma numerów wierzchołków ani wag więc nie można się zorientować co jest co.
BTW ten kod to masakra...

0

Witam wszystkich forumowiczów.

Byłby w stanie ktoś wytłumaczyć w jaki sposób wyznaczyć złożoność obliczeniową dla tego algorytmu?

Dziękuję za każdą pomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0