Графтар 2. Графтар теориясының негізгі анықтамалары
жүктеу/скачать 332,21 Kb. Pdf көрінісі
|
| 12.4 Дейкстр алгоритмі
Көптеген авторлардың пікірінше Дейкстр алгоритмі графта берілген екі төбе арасындағы ең қысқа маршрутты табу үшін ең тиімді алгоритм болып есептеледі. Бағытталмаған граф берілген болсын, ол 12.5-суретінде көрсетілген. Дейкстр алгоритмінде үш массивті қолдану керек, олардың өлшемі граф төбелерінің санына сәйкес болады. Бірінші массив - «тұрақты» төбелер массиві графтың берілген төбесінен барлық қалған төбелеріне дейінгі ең қысқа маршруттарды сақтайды. Массивке бірінші болып бірінші төбенің нөмері жазылады (осы төбелер арқылы графтың басқа төбелеріне үшін ең қысқа ара қашықтық анықталады). Массивтің атауы таңдап алынған төбелердің атауларына сәйкес болады. Дейкстр алгоритмі бойынша графтың барлық төбелері «уақытша» болып жарияланады, ал таңдап алынған төбелер «тұрақты» деп аталады. Бірінші төбе «тұрақты» болып жарияланады. Екінші массив графтың берілген төбесінен барлық қалған төбелеріне дейінгі ең қысқа арақашықтықты сақтайды. Бірінші болып оған таңдап алынған төбе нөмеріне сәйкес сыбайлас матрицасының жолы көшіріліп жазылады. Графтың сыбайлас матрицасы 12.6-кестеде көрсетілген. Үшінші логикалық типтегі массивте графтың таңдап алынған (тұрақты) төбелер жазылады. Алғашында графтың «тұрақты» төбесі ретінде бірінші төбе ғана бола алады. Одан кейін «уақытша» төбе таңдалады, бірінші (тұрақты) төбеден осы төбеге дейінгі аралық ең қысқа болуы керек. Осы төбе k төбесі болып жарияланады. Графтың «тұрақты» төбесінен барлық «уақытша» төбеге дейінгі барлық маршруттар тікелей және k төбесі арқылы тексеріледі. ең қысқа аралықтар екінші массивке жазылады. Ал, егер ең қысқа арақашықтықтың маршруты k төбесі арқылы өтетін болса, онда бірінші массивке сәйкес позицияда k жазылады.
12.6-кесте – 12.5-суреттегі графтың сыбайлас матрицасы
12.5–сурет – Қарапайым бағытталмаған граф Ары қарай k төбесі «тұрақты» болып жарияланады (ол үшінші массивте орындалады). Графтың келесі төбесін іздеу алгоритмі жаңа «тұрақты» төбеге қатысты қайталанады. Бірінші төбенің нөмері 0-ге тең деп жорамалдайық. Онда post[…]-бірінші массив нөлдерден тұрады. Екінші массивте, яғни ең қысқа қышықтықтар массивінде сыбайлас матрицаның нөлінші жолының мәндері жазылады:
0 1 2 3 4 5 6 7 8 d[min] – 0 3 1000 4 1000 1000 1000 1000 1000
Үшінші масссив, яғни таңдап алынған (выбранный) төбелер массивінің мәндері 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 1 2 3 4 5 6 7 8 d[min] – 0 3 7 4 1000 1000 1000 10 1000
0 1 2 3 4 5 6 7 8 post[…] – 0 0 1 0 0 0 0 1 0 Бұл 0-2 төбелерінің арасындағы ең қысқа арақашықтық 7-ге тең болатынын білдіреді. Таңдап алынған k төбесін t[k]=false «тұрақтысымен» жариялаймыз және осы төбеге қатысты процесс қайталанып отырады. Бағдарлама коды: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { public static int[,] a = new int[9, 9] {{ 0, 3,1000, 4,1000,1000,1000,1000,1000}, { 3, 0, 4,1000,1000,1000,1000, 7,1000}, {1000, 4, 0, 5, 2, 4, 4, 6, 9}, { 4,1000, 5, 0, 6,1000,1000,1000,1000}, {1000,1000, 2, 6, 0, 5,1000,1000,1000}, {1000,1000, 4,1000, 5, 0, 3,1000, 4}, {1000,1000, 4,1000,1000, 3, 0,1000, 4}, {1000, 7, 6,1000,1000,1000,1000, 0, 8}, {1000,1000, 9,1000,1000, 4, 4, 8, 0}}; public static int[] d = new int[10]; public static int[] post = new int[10]; public static bool[] t = new bool[10]; public static int i, j, p, k, minras; public static void poisk() { //алғышарттар minras = 0; for (i = 0; i < 9; i++) { post[i] = 0; t[i] = true; d[i] = a[0, i]; }
t[0] = false; post[0] = 0; for (i = 0; i < 8; i++) {
// k төбесін іздеу minras = 1000; for (j = 0; j < 9; j++) if ((t[j] == true) && (minras > d[j])) { minras = d[j]; k = j; } // k төбесі аркылы маршруттарды іздеу және минимальді қашықтықты табу t[k] = false; 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; }
} }
public static void print() {
// сыбайлас матрицаны шығару Console.WriteLine("Sibailas matrisani shigary: "); for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) Console.Write("\t" + a[i, j]); Console.WriteLine(); }
Console.WriteLine(); // минимальді қашықтықтарды сақтайтын массивті шығару for (i = 0; i < 9; i++) Console.Write("\t" + i); Console.WriteLine(); for (i = 0; i < 9; i++) Console.Write("\t" + d[i]); Console.WriteLine(); //маршруттар массивін шығару for (i = 0; i < 9; i++) Console.Write("\t" + post[i]); Console.WriteLine(); // графтың 0-і төбесінен бастап 8-і төбесіне дейін маршрутты шығару p = 8;
Console.Write("Songi tobe = 8 "); do {
p = post[p]; Console.Write("\t" + p); } while (p != 0); Console.WriteLine(); Console.WriteLine("Bastapki tobe = 0 "); } static void Main(string[] args) { poisk(); print(); Console.ReadLine(); } }
} Бағдарлама жұмысы: Sibailas matrisani shigary: 0 3 1000 4 1000 1000 1000 1000 1000 3 0 4 1000 1000 1000 1000 7 1000 1000 4 0 5 2 4 4 6 9 4 1000 5 0 6 1000 1000 1000 1000 1000 1000 2 6 0 5 1000 1000 1000 1000 1000 4 1000 5 0 3 1000 4 1000 1000 4 1000 1000 3 0 1000 4 1000 7 6 1000 1000 1000 1000 0 8 1000 1000 9 1000 1000 4 4 8 0
0 1 2 3 4 5 6 7 8 0 3 7 4 9 11 11 10 15 0 0 1 0 2 2 2 1 5 Songi tobe = 8 5 2 1 0 Bastapki tobe = 0
Бағдарлама жұмысының нәтижесі – екі массивті шығару, яғни графтың берілген төбесінен қалған төбелеріне дейінгі ең қысқа аралықтар мен ең қысқа маршруттардың массивтері. Мысал ретінде графтың 0-ші төбесінен 8-ші төбесіне дейінгі ең қысқа маршрут қарастырылады 8-ші мен 0-ші төбелерінің арасындағы ең қысқа аралық 15-ке тең. Орын ауыстыру маршруты: 8 – 5 – 2 – 1 – 0.
жүктеу/скачать 332,21 Kb. Достарыңызбен бөлісу:
|