Algorithm Dijkstra

Algorithm Dijkstra (neu algorithm Llwybr Lleiaf Cyntaf Dijkstra) yw algorithm gyfer canfod llwybrau byrraf rhwng fertigau mewn graff. Gall cael ei ddefnyddio, er enghraifft, canfod llwybrau lleiaf mewn rhwydweithiau ffyrdd. Fe’i crëwyd gan y gwyddonydd cyfrifiadurol Edsger W. Dijkstra ym 1956 a’i gyhoeddi tair blynedd yn ddiweddarach.

Ar gyfer fertig ffynhonnell benodol yn y graff, mae'r algorithm yn dod o hyd i'r llwybr byrraf rhwng y fertig hwnnw a phob un arall, gan gynhyrchu coeden llwybr byrraf. Gellir ei ddefnyddio hefyd ar gyfer dod o hyd i'r llwybrau byrraf o fertig sengl i fertig cyrchfan sengl trwy stopio'r yr algorithm unwaith y bydd y llwybr byrraf i'r fertig cyrchfan wedi'i ganfod. Dyma oedd fersiwn gwreiddiol Dijkstra.

Er enghraifft, os yw nodau'r graff yn cynrychioli dinasoedd a chostau llwybr ymyl yn cynrychioli pellteroedd gyrru rhwng parau o ddinasoedd wedi'u cysylltu gan ffordd uniongyrchol (er symlrwydd, anwybyddu goleuadau coch a rhwystrau eraill), gellir defnyddio algorithm Dijkstra i ddod o hyd i'r llwybr byrraf rhwng un ddinas a'r holl ddinasoedd eraill.
 Hanes 
Meddyliodd Dijkstra am y broblem llwybr byrraf wrth weithio yn y Ganolfan Fathemategol yn Amsterdam ym 1956 fel rhaglennydd i arddangos galluoedd cyfrifiadur newydd o'r enw ARMAC. Ei amcan oedd dewis problem ac ateb (a fyddai'n cael ei gynhyrchu gan gyfrifiadur) y gallai pobl nad ydynt yn gyfrifiaduron ei ddeall. Dyluniodd yr algorithm llwybr byrraf a'i weithredu yn ddiweddarach ar gyfer ARMAC ar gyfer map o 64 o ddinasoedd yn yr Iseldiroedd (64, fel y byddai 6 did yn ddigonol i amgodio rhif y ddinas).

Blwyddyn yn ddiweddarach, daeth ar draws problem arall gan beirianwyr caledwedd a oedd yn gweithio ar gyfrifiadur nesaf y sefydliad: y broblem o leihau faint o wifren sydd ei angen i gysylltu'r pinnau ar banel cefn y peiriant. Fel ateb, fe wnaeth ail-ddarganfod yr algorithm Prim i ganfod coed rhychwantu lleiaf. Cyhoeddodd Dijkstra yr algorithm ym 1959, ddwy flynedd ar ôl Prim a 29 mlynedd ar ôl y darganfyddwr gwreiddiol Jarník.V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)

 Algorithm 
bawd|Darlun o algorithm Dijkstra yn dod o hyd i lwybr o fertig cychwyn (chwith isaf, coch) i fertig amcan (dde uchaf, gwyrdd). Mae cylchoedd gwag yn cynrychioli'r set heb eu hymweld eto. Y cylchoedd lliw i'r fertigau sydd wedi eu hymweld, gyda lliw yn cynrychioli'r pellter: y gwyrddach, yr agosaf.
Caiff y fertig yr ydym yn dechrau arno ei alw'r fertig cychwynnol. Gadewch i bellter fertig Y fod y pellter o'r fertig cychwynnol i Y. Mae algorithm Dijkstra yn aseinio rhai gwerthoedd pellter cychwynnol i'r fertigau, ac yn ceisio eu gwella gam wrth gam.

 Marciwch bob fertig fel heb eu hymweld. Creu set o'r holl nodau heb eu hymweld, o'r enw'r set heb eu hymweld.
 Aseiniwch werth pellter petrus i bob fertig: gosodwch ef i sero ar gyfer ein fertig cychwynnol ac i anfeidredd ar gyfer pob fertig arall. Gosodwch y fertig cychwynnol fel y fertig presennol.
 Ar gyfer y fertig presennol, ystyriwch ei holl gymdogion heb eu hymweld, a chyfrifwch eu pellteroedd petrus trwy'r fertig presennol. Cymharwch y pellter petrus newydd ei gyfrifo â'r gwerth pellter cyfredol, a aseiniwch iddo'r un lleiaf. Er enghraifft, os yw'r fertig cyfredol A wedi'i farcio â phellter o 6, a bod gan yr ymyl sy'n ei gysylltu â chymydog B hyd 2, yna'r pellter i B trwy A fydd 6 + 2 = 8. Os oedd B wedi'i farcio o'r blaen gyda phellter mwy nag 8 yna newidiwch ef i 8. Fel arall, cadwch y gwerth pellter cyfredol.
 Pan fyddwn wedi gorffen ystyried holl gymdogion y fertig presennol sydd heb eu hymweld, marciwch y fertig presennol fel wedi ei ymweld, a'i dynnu o'r set heb eu hymweld. Ni fydd fertig sydd wedi ei ymweld byth yn cael ei wirio eto.
 Os yw'r fertig cyrchfan wedi'i farcio fel wedi ei ymweld (wrth gynllunio llwybr rhwng dau nod penodol), neu os yw'r pellter petrus lleiaf ymhlith y nodau yn y set heb eu hymweld yn anfeidredd (wrth gynhyrchu coeden pellter lleiaf), yna stopiwch. Mae'r algorithm wedi gorffen.
 Fel arall, dewiswch y nod heb ei ymweld sydd wedi'i farcio â'r pellter petrus lleiaf, gosodwch fel y "fertig presennol" newydd, ac ewch yn ôl i gam 3.

 Trafodaeth 

Nid yw'r algorithm hwn yn gwneud unrhyw ymdrech i "archwilio" yn uniongyrchol tuag at y gyrchfan. Yn hytrach, yr unig ystyriaeth wrth bennu'r fertig "presennol" nesaf yw ei bellter o'r fertig cychwyn. Felly mae'r algorithm hwn yn ehangu tuag allan o'r man cychwyn, gan ystyried ar y pryd pob nod sy'n agosach o ran pellter llwybr byrraf nes iddo gyrraedd y gyrchfan. Wrth ddeall yr algorithm fel hyn, mae'n amlwg sut mae'r algorithm bendant yn dod o hyd i'r llwybr byrraf. Fodd bynnag, mae hefyd yn datgelu un o wendidau'r algorithm: mae'n araf mewn rhai topolegau.

 Cymwysiadau 
Mae llwybrau cost leiaf yn cael eu cyfrifo er enghraifft er mwyn sefydlu traciau llinellau trydan neu bibellau olew. Defnyddiwyd yr algorithm hefyd i gyfrifo'r llwybrau troed pellter hir gorau posibl yn Ethiopia a'u cyferbynnu â beth ddigwyddir mewn gwirionedd.Nyssen, J., Tesfaalem Ghebreyohannes, Hailemariam Meaza, Dondeyne, S., 2020. Exploration of a medieval African map (Aksum, Ethiopia) – How do historical maps fit with topography? In: De Ryck, M., Nyssen, J., Van Acker, K., Van Roy, W., Liber Amicorum: Philippe De Maeyer In Kaart. Wachtebeke (Belgium): University Press: 165-178.

 Cyfeiriadau