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

Adibide batez erakutsiko da algoritmoaren garapena. Honako grafo hau harturik, A punturik beste puntu guztietarako ibilbide laburrena eman behar da Dijkstra-ren algoritmoaren bitartez. Kalkulu eta pausoak beheko taulan azaltzen dira:

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}

Jarraitu beharreko pausoak hauek dira:

• 1. pausoa: A puntuarekin loturik dauden puntu guztietarako distantziak ezartzen dira lehenengo lerro batean, A puntutik abiatzen direla adieraziz. Distantzia txikiena giltzen artean jartzen da.