b'\n_START_ARTICLE_\nAlgorytm Dijkstry\n_START_SECTION_\nDzia\xc5\x82anie\n_START_PARAGRAPH_\nMaj\xc4\x85c dany graf z wyr\xc3\xb3\xc5\xbcnionym wierzcho\xc5\x82kiem (\xc5\xbar\xc3\xb3d\xc5\x82em) algorytm znajduje odleg\xc5\x82o\xc5\x9bci od \xc5\xbar\xc3\xb3d\xc5\x82a do wszystkich pozosta\xc5\x82ych wierzcho\xc5\x82k\xc3\xb3w. \xc5\x81atwo zmodyfikowa\xc4\x87 go tak, aby szuka\xc5\x82 wy\xc5\x82\xc4\x85cznie (najkr\xc3\xb3tszej) \xc5\x9bcie\xc5\xbcki do jednego ustalonego wierzcho\xc5\x82ka, po prostu przerywaj\xc4\x85c dzia\xc5\x82anie w momencie doj\xc5\x9bcia do wierzcho\xc5\x82ka docelowego, b\xc4\x85d\xc5\xba transponuj\xc4\x85c tablic\xc4\x99 incydencji grafu._NEWLINE_Algorytm Dijkstry znajduje w grafie wszystkie najkr\xc3\xb3tsze \xc5\x9bcie\xc5\xbcki pomi\xc4\x99dzy wybranym wierzcho\xc5\x82kiem a wszystkimi pozosta\xc5\x82ymi, przy okazji wyliczaj\xc4\x85c r\xc3\xb3wnie\xc5\xbc koszt przej\xc5\x9bcia ka\xc5\xbcdej z tych \xc5\x9bcie\xc5\xbcek._NEWLINE_Algorytm Dijkstry jest przyk\xc5\x82adem algorytmu zach\xc5\x82annego.\n_START_SECTION_\nZastosowanie\n_START_PARAGRAPH_\nZ algorytmu Dijkstry mo\xc5\xbcna skorzysta\xc4\x87 przy obliczaniu najkr\xc3\xb3tszej drogi do danej miejscowo\xc5\x9bci. Wystarczy przyj\xc4\x85\xc4\x87, \xc5\xbce ka\xc5\xbcdy z punkt\xc3\xb3w skrzy\xc5\xbcowa\xc5\x84 dr\xc3\xb3g to jeden z wierzcho\xc5\x82k\xc3\xb3w grafu, a odleg\xc5\x82o\xc5\x9bci mi\xc4\x99dzy punktami to wagi kraw\xc4\x99dzi._NEWLINE_Jest cz\xc4\x99sto u\xc5\xbcywany w sieciach komputerowych, np. przy trasowaniu (przyk\xc5\x82adowo w protokole OSPF).\n_START_SECTION_\nPseudokod\n_START_PARAGRAPH_\nDijkstra(G,w,s):_NEWLINE_   dla ka\xc5\xbcdego wierzcho\xc5\x82ka v w V[G] wykonaj_NEWLINE_      d[v]\xc2\xa0:= niesko\xc5\x84czono\xc5\x9b\xc4\x87_NEWLINE_      poprzednik[v]\xc2\xa0:= niezdefiniowane_NEWLINE_   d[s]\xc2\xa0:= 0_NEWLINE_   Q\xc2\xa0:= V_NEWLINE_   dop\xc3\xb3ki Q niepuste wykonaj_NEWLINE_      u\xc2\xa0:= Zdejmij_Min(Q)_NEWLINE_      dla ka\xc5\xbcdego wierzcho\xc5\x82ka v \xe2\x80\x93 s\xc4\x85siada u wykonaj_NEWLINE_         je\xc5\xbceli d[v] > d[u] + w(u, v) to_NEWLINE_            d[v]\xc2\xa0:= d[u] + w(u, v)_NEWLINE_            poprzednik[v]\xc2\xa0:= u_NEWLINE__NEWLINE_   Wy\xc5\x9bwietl("Droga wynosi: " + d[v])\n_START_SECTION_\nProblemy i algorytmy pokrewne\n_START_PARAGRAPH_\nAlgorytm Dijkstry nie dzia\xc5\x82a, je\xc5\x9bli w grafie wyst\xc4\x99puj\xc4\x85 kraw\xc4\x99dzie z ujemnymi wagami \xe2\x80\x93 w tym wypadku u\xc5\xbcywa si\xc4\x99 wolniejszego, lecz bardziej og\xc3\xb3lnego algorytmu Bellmana-Forda. Je\xc5\x9bli graf nie jest wa\xc5\xbcony (wszystkie wagi maj\xc4\x85 wielko\xc5\x9b\xc4\x87 1), zamiast algorytmu Dijkstry wystarczy algorytm przeszukiwania grafu wszerz._NEWLINE_Algorytm A* jest pewnym uog\xc3\xb3lnieniem algorytmu Dijkstry, kt\xc3\xb3re pozwala przeszukiwa\xc4\x87 tylko cz\xc4\x99\xc5\x9b\xc4\x87 grafu, jednak wymaga dodatkowej wst\xc4\x99pnej informacji (heurystyki) o odleg\xc5\x82o\xc5\x9bciach wierzcho\xc5\x82k\xc3\xb3w._NEWLINE_Algorytm Prima znajdowania minimalnego drzewa rozpinaj\xc4\x85cego oparty jest o bardzo podobny pomys\xc5\x82 co algorytm Dijkstry.'