FOR (K=0;K<6;K++)
FOR (I=0;I<6;I++)
FOR (J=0;J<6;J++)
IF(A[I,J]>A[I,K]+A[K,J])
A[I,J]=A[I,K]+A[K,J];
Console.WriteLine("Печатаем новую матрицу : ");
for (i=0;i<6;i++)
{
for (j=0;j<6;j++)
Console.Write("\t" + a[i,j]);
Console.WriteLine();
}
Console.ReadLine();
}
Флойд алгоритмі
Е ң қысқа жолды табу
Бағдарлама жұмысының
нәтижесі:
Флойд алгоритмі
Кесте - графтың сыбайлас матрицасы
Бағдарламаның (алгоритмнің) кемшіліктері:
– ең қысқы арақышықтықтың маршруты анықталмайды;
– алгоритмнің есептеу тиімділігі n-нің 3-ші дәрежесіне пропорционал (мұнда n – граф төбелерінің саны), ол n-нің үлкен мәндерінде тиімсіз болып келеді.
Флойд алгоритмі
Дейкстр алгоритмі
Көптеген авторлардың пікірінше Дейкстр алгоритмі графта берілген екі төбе арасындағы ең қысқа маршрутты табу үшін ең тиімді алгоритм болып есептеледі.
Бағытталмаған граф берілген болсын, ол 12.5-суретінде көрсетілген.
Қарапайым бағытталмаған граф
Графтың сыбайлас матрицасы
Бағытталмаған граф берілген болсын, ол жоғарыдағы суретте көрсетілген. Дейкстр алгоритмінде үш массивті қолдану керек. Олардың өлшемі граф төбелерінің санына сәйкес болады.
Дейкстр алгоритмі
Бірінші массив - «тұрақты» төбелер массиві, графтың берілген төбесінен барлық қалған төбелеріне дейінгі ең қысқа маршруттарды сақтайды.
Массивке бірінші болып бірінші төбенің нөмері жазылады (осы төбелер арқылы графтың басқа төбелеріне үшін ең қысқа ара қашықтық анықталады).
Дейкстр алгоритмі бойынша графтың барлық төбелері «уақытша» болып жарияланады, ал таңдап алынған төбелер «тұрақты» деп аталады. Бірінші төбе «тұрақты» болып жарияланады. (post[…])
Дейкстр алгоритмі
Екінші массив графтың берілген төбесінен барлық қалған төбелеріне дейінгі ең қысқа арақашықтықты сақтайды.
Бірінші болып оған таңдап алынған төбе нөмеріне сәйкес сыбайлас матрицасының жолы (строка матрицы смежности) көшіріліп жазылады. Графтың сыбайлас матрицасы жоғарыда, кестеде көрсетілген (d[min] ).
Достарыңызбен бөлісу: |
