Zasada działania tego algorytmu jest prosta. Na początku ustawiamy sobie wyniki do każdego punktu jako nieskończoność.
Z obranego punktu startowego wyszukujemy wychodzące krawędzie i zapisujemy ich wagi jako wyniki do poszczególnych wierzchołków, do których wchodzą krawędzie z punktu startowego.
Potem dla każdego z tych wierzchołków rozpatrzmy wychodzące krawędzie na podobnej zasadzie co wcześniej, z tym, że nie zapisujemy wag jako wyniki, tylko sprawdzamy czy suma wagi danej krawędzi i wyniku do wierzchołka wychodzącego jest mniejsza niż wynik dla wierzchołka, do którego krawędź wchodzi. Jeśli tak to nadpisujemy wynik.
Czynność tę powtarzamy tak długo, że nie będziemy mogli już dokonać żadnej zmiany.
To tyle teorii… Może trochę pogmatwałem, ale mam nadzieję, że zrozumiecie 😉
Teraz kod implementacyjny:
Kod stary:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
program dijkstra; const MAX=1000; NIESKONCZONOSC=high(integer); var wychodzace,tab:array[1..MAX] of array[1..MAX] of integer; wyniki,liczniki:array[1..MAX] of integer; stan:array[1..MAX] of integer; zrobione:boolean; i,j,n,wierzch,zkad,gdzie,ile,start,licznik:integer; begin writeln('podaj ilosc wierzcholkow:'); readln(wierzch); for i:=1 to wierzch do begin liczniki:=0; wyniki:=NIESKONCZONOSC; end; writeln('podaj ilosc krawedzi:'); readln(n); writeln('podaj te krawedzie:'); for i:=1 to n do begin readln(zkad,gdzie,ile); tab[zkad,gdzie]:=ile; inc(liczniki[zkad]); wychodzace[zkad,liczniki[zkad]]:=gdzie; end; writeln('podaj od jakiego wierzcholka chcesz przejsc:'); readln(start); writeln('koszty polaczen:'); for i:=1 to liczniki[start] do begin wyniki[wychodzace[start,i]]:=tab[start,wychodzace[start,i]]; stan[wychodzace[start,i]]:=2; end; stan[start]:=1; wyniki[start]:=0; licznik:=1; repeat begin zrobione:=false; inc(licznik); for i:=1 to wierzch do begin if stan=licznik then begin for j:=1 to liczniki do begin if wyniki+tab[i,wychodzace[i,j]]<wyniki[wychodzace[i,j]] then="" <br=""> begin wyniki[wychodzace[i,j]]:=wyniki+tab[i,wychodzace[i,j]]; stan[wychodzace[i,j]]:=licznik+1; zrobione:=true; end; end; stan:=1; end; end; end; until zrobione=false; for i:=1 to wierzch do begin if wyniki=NIESKONCZONOSC then writeln('do: ',i,' nie ma drogi') else if i=start then writeln(i,' to punkt startowy') else writeln('do: ',i,' koszt: ',wyniki); end; readln; end.</wyniki[wychodzace[i,j]]> |
kod nowy:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
program dijkstra; const MAX=1000; NIESKONCZONOSC=high(integer); var wychodzace,tab:array[1..MAX] of array[1..MAX] of integer; wyniki,liczniki:array[1..MAX] of integer; dorozpatrzenia1,dorozpatrzenia2:array[1..MAX] of integer; rozpatrzamy:boolean; i,j,k,n,wierzch,zkad,gdzie,ile,start,licznik,iledorozp1,iledorozp2:integer; begin writeln('podaj ilosc wierzcholkow:'); readln(wierzch); for i:=1 to wierzch do begin liczniki:=0; wyniki:=NIESKONCZONOSC; end; writeln('podaj ilosc krawedzi:'); readln(n); writeln('podaj te krawedzie:'); for i:=1 to n do begin readln(zkad,gdzie,ile); tab[zkad,gdzie]:=ile; inc(liczniki[zkad]); wychodzace[zkad,liczniki[zkad]]:=gdzie; end; writeln('podaj od jakiego wierzcholka chcesz przejsc:'); readln(start); writeln('koszty polaczen:'); iledorozp1:=0; iledorozp2:=0; //wychodzące dla punktu startowego for i:=1 to liczniki[start] do begin wyniki[wychodzace[start,i]]:=tab[start,wychodzace[start,i]]; inc(iledorozp1); dorozpatrzenia1[iledorozp1]:=wychodzace[start,i]; end; wyniki[start]:=0; licznik:=1; rozpatrzamy:=false; //wychodzące z pozostałych punktów while (iledorozp1>0) or (iledorozp2>0) do begin inc(licznik); if rozpatrzamy=false then begin for i:=1 to iledorozp1 do begin for j:=1 to liczniki[dorozpatrzenia1] do begin k:=dorozpatrzenia1; if wyniki[k]+tab[k,wychodzace[k,j]]<wyniki[wychodzace[k,j]] then="" <br=""> begin wyniki[wychodzace[k,j]]:=wyniki[k]+tab[k,wychodzace[k,j]]; inc(iledorozp2); dorozpatrzenia2[iledorozp2]:=wychodzace[k,j]; dorozpatrzenia1:=0; end; end; end; rozpatrzamy:=true; iledorozp1:=0; end else begin for i:=1 to iledorozp2 do begin for j:=1 to liczniki[dorozpatrzenia2] do begin k:=dorozpatrzenia2; if wyniki[k]+tab[k,wychodzace[k,j]]<wyniki[wychodzace[k,j]] then="" <br=""> begin wyniki[wychodzace[k,j]]:=wyniki[k]+tab[k,wychodzace[k,j]]; inc(iledorozp1); dorozpatrzenia1[iledorozp1]:=wychodzace[k,j]; dorozpatrzenia2:=0; end; end; end; rozpatrzamy:=false; iledorozp2:=0; end; end; //wypisywanie wyniku for i:=1 to wierzch do begin if wyniki=NIESKONCZONOSC then writeln('do: ',i,' nie ma drogi') else if i=start then writeln(i,' to punkt startowy') else writeln('do: ',i,' koszt: ',wyniki); end; readln; end.</wyniki[wychodzace[k,j]]></wyniki[wychodzace[k,j]]> |
uwaga:
Stała MAX określa maksymalną ilość wierzchołków, jakie może zawierać graf 😉
I to właściwie na tyle… Starałem się zrobić, aby działał on jak najszybciej, choć nie wiem czy mi się to udało. Jeśli ktoś znalazłby błąd lub miałby jakieś sugestie to bardzo proszę o poprawienie ;p Kod pisałem sam, nie korzystając z żadnych pomocy lub innych algorytmów, więc nie jest to wzorcówka 😉
//edit: dodałem wcięcia ;p
//edit2: dodałem drugą wersję, która powinna działać odrobinę szybciej 😉
//przepraszam, że się wcinam w artykuł, ale chciałbym kod wkleić
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
program gen; var n,i,x:longint; begin readln(n); writeln(n); writeln(n*(n-1) div 2); for i:=n downto 2 do begin writeln(i,' ',i-1,' ',1); for x := i-2 downto 1 do writeln(i,' ',x,' ',2*i+n); end; writeln(n); end. |
Program generujący przypadek, dla którego algorytm działa w czasie O(n^3).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
(...) i,j,n,wierzch,zkad,gdzie,ile,start,licznik:integer; przLicz,wierzLicz,krawLicz:longint; begin przLicz := 0; wierzLicz := 0; krawLicz := 0; writeln('podaj ilosc wierzcholkow:'); (...) repeat begin inc(przLicz); zrobione:=false; inc(licznik); for i:=1 to wierzch do begin if stan=licznik then begin inc(wierzLicz); for j:=1 to liczniki do begin inc(krawLicz); if wyniki+tab[i,wychodzace[i,j]]<wyniki[wychodzace[i,j]] then="" <br=""> begin wyniki[wychodzace[i,j]]:=wyniki+tab[i,wychodzace[i,j]]; stan[wychodzace[i,j]]:=licznik+1; zrobione:=true; end; end; stan:=1; end; end; end; until zrobione=false; (...) writeln('Przebiegow petli: ',przLicz); writeln('Rozwazen wierzcholkow: ',wierzLicz); writeln('Rozwazen krawedzi: ',krawLicz); readln; end. </wyniki[wychodzace[i,j]]> |
Zmiany w kodzie pierwszego programu pozwalające na zliczenie przebiegów pętli, rozważanych wierzchołków oraz rozważanych krawędzi.
Można udowodnić, że przebiegów pętli (w grafie generowanym przez podany generator) jest n, rozważeń wierzchołków n(n-1)/2, zaś rozważonych krawędzi (n-2)(n-1)n/6, a to ostatnie jest O(n^3).