Dijkstraren algoritmo

Grafo teorian, Dijkstraren algoritmoa, Edsger Dijkstra informatikariak asmatua 1959. urtean, haztapen positiboak (kostuak, distantziak, esaterako) dituen grafo bateko puntu edo erpinen ezberdinen arteko ibilbide laburrena aurkitzeko algoritmoa da.

Jatorritzat hartzen den puntu edo erpin batetik abiaturik, algoritmoak grafoko beste puntu edo erpin guztietarako kostu edo distantzia txikiena duen ibilbidea ematen du. Dijkstra-ren algoritmoa algoritmo irenskorra da, pauso bakoitzean kostu edo distantzia txikiena duen ibilbidea aukeratzen baitu.

Algoritmoaren garapena

Nondik: A --->	B	C	D	E	F	G	H
1:A	{20-A}	$\infty$	80-A	$\infty$	$\infty$	90-A	$\infty$
2:B	{20-A}	$\infty$	80-A	$\infty$	{30-B}	90-A	$\infty$
3:F	{20-A}	{40-F}	70-F	$\infty$	{30-B}	90-A	$\infty$
4:C	{20-A}	{40-F}	{50-C}	$\infty$	{30-B}	90-A	60-C
5:D	{20-A}	{40-F}	{50-C}	$\infty$	{30-B}	70-D	{60-C}
6:H	{20-A}	{40-F}	{50-C}	$\infty$	{30-B}	{70-D}	{60-C}
7:G	{20-A}	{40-F}	{50-C}	$\{\infty \}$	{30-B}	{70-D}	{60-C}