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)	{20-A}	$\infty$	80-A	$\infty$	{30-B}	90-A	$\infty$
3:F (30)	{20-A}	{40-F}	70-F	$\infty$	{30-B}	90-A	$\infty$
4:C (40)	{20-A}	{40-F}	{50-C}	$\infty$	{30-B}	90-A	60-C
5:D (50)	{20-A}	{40-F}	{50-C}	$\infty$	{30-B}	70-D	{60-C}
6:H (60)	{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: D zutabekoa da.

• 4. pausoa: Ctik F, H edo Dra joan daiteke. Fra 40+50=90ko distantziaz joan daiteke. 90 balioak aurreko lerrokoa hobetzen ez duenez, berdin geratzen da. Hra 40+20=60ko distantziaz joan daiteke. Aurreko lerroko infinitua baino hobea denez, 60-C jartzen da. Dra 40+10=50eko distantziaz joan daiteke. Aurreko lerroko 70 baino hobea denez, aldatu egiten da, horretarako Ctik igaro behar dela adieraziz. Lerroan giltzatu gabekoetan txikiena giltzatzen da: D zutabekoa.

• 5. pausoa: aurreko lerroan giltzak jarri zaizkion zutabetik abiatzen da, Dtik alegia. Dtik Cra edo Gra joan daiteke. Cra 50+10=60 ditantziaz joan daiteke, baina aurreko lerroko soluzioa hobetzen ez duenez, baztertu egiten da eta aurreko lerroko berdina uzten da. Gra 50+20=70ko distantziaz joan daiteke, Dtik. Aurreko lerroko 90eko soluzioa hobetzen duenez, 70-D jartzen dugu. Lerroko beste guztiak berdin uzten dira. Giltzarik gabekoetan H zutabekoa, 60-C alegia, da txikiena eta bera giltzatzen da ondorioz.

• 6. pausoa: Htik abiatuz abiatuz, ezin da inora joan. Beraz, lerroa berdin geratzen da. Giltzatu gabeko txikiena giltzatzen da: G zutabea.

• 7. pausoa: Gtik Era joan daitekeen bakarrik aztertu behar da. Ezin denez joan, lerroa berdin geratzen da eta E zutabea ixten da, infinitu balioarekin, Era joan ezin daitekeela adieraziz horrela. Ara bai joan daitekeela, baina ez dago Arentzat zutaberik, helburua ez baita inoiz Ara joan edo itzultzea.

Honela, adibidez Gra joateko ibilbide laburrena zein den jakiteko, G zutabeko azkena begiratzen da: 70-D. 70eko distantziaz joan behar da, Dtik igaroz. Dra Ctik joan behar da, D zutabeko azkena begiratuz. Cra Ftik, Fra Btik eta Bra Atik, hurrenez hurren, beti zutabeko azkenean begiratuz. Ibilbidea hau izango da beraz: ABFCDG, 70ko distantziaz.

Kanpo estekak

• Datuak: Q8548
• Multimedia: Dijkstra's algorithm / Q8548