Algorithm Dijkstra

bawd|Animeiddiad yn dangos algorithm Dijkstra ar ei waith.
**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. 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). Cyhoeddodd Dijkstra yr algorithm ym 1959, ddwy flynedd ar ôl Prim a 29 mlynedd ar ôl y darganfyddwr gwreiddiol Jarník.

## 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.

## Cyfeiriadau