Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszych ścieżek z wybranego wierzchołka do pozostałych wierzchołków w grafie o nieujemnych wagach krawędzi.
Działanie Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków. Łatwo jest zmodyfikować go tak, aby szukał wyłącznie (najkrótszej) ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego, bądź transponując tablicę incydencji grafu.
Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, przy okazji wyliczając również koszt przejścia każdej z tych ścieżek..
Algorytm Dijkstry jest przykładem algorytmu zachłannegoAlgorytm Dijkstry..
Algorytm Przez oznaczamy wierzchołek źródłowy, to waga krawędzi w grafie. Stwórz tablicę odległości od źródła dla wszystkich wierzchołków grafu. Na początku zaś dla wszystkich pozostałych wierzchołków. Utwórz kolejkę priorytetową wszystkich wierzchołków grafu.