Бағдарламалу технологиясы



жүктеу 1,63 Mb.
бет66/73
Дата03.02.2022
өлшемі1,63 Mb.
#35497
түріОқулық
1   ...   62   63   64   65   66   67   68   69   ...   73
Ба?дарламалу технологиясы

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.


жүктеу 1,63 Mb.

Достарыңызбен бөлісу:
1   ...   62   63   64   65   66   67   68   69   ...   73




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау