Дейкстралгоритмі Үшінші логикалық типтегі массивте графтың таңдалған (тұрақты) төбелері жазылады. Алғашында графтың «тұрақты» төбесі ретінде бірінші төбе ғана белгіленеді (t[0]).
Одан кейін «уақытша» төбе таңдалады, бірінші (тұрақты) төбеден осы төбеге дейінгі аралық ең қысқа болуы керек. Осы төбе k төбесі болып жарияланады.
Графтың «тұрақты» төбесінен барлық «уақытша» төбеге дейінгі барлық маршруттар тікелей және k төбесі арқылы тексеріледі.
Ең қысқа аралықтар екінші массивке жазылады. Ал, егер ең қысқа арақашықтықтың маршруты k төбесі арқылы өтетін болса, онда бірінші массивке сәйкес позицияда k жазылады.
Ары қарай k төбесі «тұрақты» болып жарияланады (ол үшінші массивте орындалады). Графтың келесі төбесін іздеу алгоритмі жаңа «тұрақты» төбеге қатысты қайталанады.
Дейкстр алгоритмі Бірінші төбенің нөмері 0-ге тең деп жорамалдайық. Онда post[…]-бірінші массив нөлдерден тұрады. Екінші массивте, яғни ең қысқа қышықтықтар массивінде сыбайлас матрицаның нөлінші жолының мәндері жазылады:
Үшінші масссив, яғни таңдап алынған (выбранный) төбелер массивінің мәндері true болады, тек нөлінші элементте ғана t[0]=false;.
0-ші төбеден басқа бір төбеге дейінгі ең қысқа аралықты таңдаймыз. Біздің жағдайымызда ол 1-ші төбе болады, оған дейінгі қашықтық 3-ке тең болады. Таңдап алынған төбе k деп аталсын. Флойд алгоритмін қолданып, алғашқы төбеден “k” төбесі арқылы өтетін қалған басқа төбелерге дейінгі барлық ең қысқа маршруттарды табамыз.
for (j=0;j<9;j++)
if ((t[j]==true)&&(d[j]>d[k]+a[k,j]))
{ d[j]=d[k]+a[k,j]; post[j]=k; }
Дейкстр алгоритмі нәтижесінде d және post массивтерінің жаңа мәнін аламыз:
Бұл 0-2 төбелерінің арасындағы ең қысқа арақашықтық 7-гетең болатынын білдіреді,
маршрут 1-і төбе арқылы өтеді.
Таңдап алынған k төбесін t[k]=false «тұрақты» деп жариялаймыз және осы төбеге қатысты процесс қайталанып отырады.
Дейкстр алгоритмі
