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 hobezina 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. A puntuarekin zuzenean loturik ez dauden puntuetarako distantziak infinitu direla ezartzen da.

• 2. pausoa: aurreko pausoan giltzen artean geratu den puntutik, B puntutik alegia, abiatzen da bigarren lerroa. B puntutik berarekin zuzenean loturik dauden puntuetarako distantziak kalkulatzen dira, B puntura giltzen artean gertatu den distantzia txikiena gehituz. Kasu honetan, Btik Fra joan daiteke, 30eko distantziaz, Atik Bra joateko 20ko distantzia hobezinari 10 gehituz, aurreko lerroko distantzia infinitua baino txikiagoa baita. Lerroko beste elementu guztiak berdin geratzen dira. Lerro osoko distantzia txikiena hartzen da, F puntura 30, eta giltzen artean jartzen dugu. F joateko ibilbide laburrena beraz, Btik igarotzen da, 30eko distantziaz. Bra joateko berriz, ibilbide hobezina Atik abiatzen da.

• 3. pausoa: 2. lerroan giltzen artean jarri den puntutik abiatzen da, Ftik alegia, bertaraino ibilbide laburrena zein den ezaguna delako.