clear
clc

r=1;                 %licznik wykonania algorytmu
T=0;
for n=5:5:100                    %20 powtórzeń algorytmu
    for l_probek=1:1:30              %liczba przebiegów
        for i=1:1:n
            for j=1:1:n
                if i~=j
                    W(i,j)=ceil(rand(1)*30)+20; %% losuje liczby do macieży wag od 30 do 50
                end
            end
        end
s=1;
t=n;
dist=[];                %% Tabela z najkrótszymi drogami
final=[];               %% Tabela logiczna
pred=[];            %% Tabela poprzedników

for v=1:n
    dist(v)=inf;                %% odległość poszczególnych węzłów od "start"
    final(v)=false;             %% ustalenie czy cecha jest tymczasowa (false) czy stala (true)
    pred(v)=-1;                 %% poprzedniki
end
 dist(s)=0;                     %% odległość ze źródła
 final(s)=true;                 %% cecha stała dla źródła
 recent=s;                      %% s jako wierzchołek, którego cecha została ostatnio ustalona
 tic;                           %% rozpoczęcie działania timera
while ~final(t)                 %% Pętla jeśli dla wierzchołka końcowego nie jest ustalona cecha stała
    for v=1:n
        if (W(recent,v)<inf) && (~final(v))     %% Waga krawędzi pomiędzy wierzchołkami recent a v jest mniejsza niż nieskonczoność i v nie jest stałe
            newlabel=dist(recent)+W(recent,v);  %% to zmienna wynosi odległość od s do recent + waga tej krawędzi
            if newlabel<dist(v)                 %% jeśli zmienna jest mniejsza od odlegóści od s do v  to:
                dist(v)=newlabel;               %% zmienna wynosi najkrótszą drogę z s do v
                pred(v)=recent;                 %% v jakos wierzchołek o ostatnio ustalonej cesze
            end
        end
    end
    temp=inf;                         %% cecha tymczasowa
    for u=1:n
        if (~final(u) && dist(u)<temp)  %% jeśli u nie jest stałe i najkrótsza droga od s do u jest mniejsza od temp
            y=u;
            temp=dist(u);       %% cecha zmienna jako najktótsza droga z s do u
        end
    end

    if temp<inf                 %% jeśli cecha zminna jest mniejsza od nieskonczoności
        final(y)=true;          %% to y jako stała
        recent=y;               %% y jakos wierzchołek o ostatniu ustalonej cesze
    else
        final(t)=true;          %% jeśli nie to wierzchołek t jest stała
    end
end
T=T+toc;            %koniec pomiaru czasu

    end
    tim(r)=T/30;            %20 sum czasów wykonania algorytmu
  r=r+1;            %inkrementacja licznika
end
z=tim(1);
poprawka=z/25;
                        %formowanie wykresu
n=[5:5:100];                            %wartości osi X
plot(n,tim,'blue' )                 %wykres czasu wykonywania algorytmu Dijkstry
hold on
plot(n,n.^2.*poprawka,'black')  %wykres teoretycznej złożoności obliczeniowej algorytmu Dijkstry
xlabel(' Liczba węzłów ');
ylabel(' Czas działania [s] ');
legend('Rzeczywisty czas działania','Teoretyczny czas działania');
tekst=['Algorytm Dijkstry'];
title(tekst);