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 (giltzen artean dagoena kenduz), 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. Ftik Cra eta Dra joan daiteke. Cra 30+10=40ko distantzia txikienaz joan daiteke orain arte (30 aurreko lerroko Ftik hartzen da), infinitu baino txikiagoa denez, 40-F jartzen da Cren zutabean. Dra 30+40=70eko distantziaz joan daiteke (30 aurreko lerroko Ftik hartuz berriz ere) Ftik abiatuz eta aurreko lerroko 80ko distantzia baino txikiagoa denez, 70eko distantzia jartzen dugu, F adieraziz. Lerroko beste balio guztiak aurreko lerroan bezala geratzen dira, F ez baita zutabe horiei dagozkien puntuetara heltzen. Lerro osoan, giltzak kenduta, balio txikiena giltzen artean jartzen da.