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

12.3 Флойд алгоритмі

Көлік туралы есептердің көптеген түрлері бар, есепте графтың әр түрлі төбелерінің арасындағы арақашықтықты анықтау немесе оны қолдану керек және осы арақашықтық ең қысқа арақашықтық болуы керек.

Графтар теориясында граф төбелерінің арасындағы ең қысқа арақашықтықты анықтайтын көптеген алгоритмдер белгілі, бірақ оның барлығы Флойд ұсынған алгоритмді негізге алады. Осы алгоритмнің кең қолданылуы төбелер арасындағы ең қысқа арақашықтықты табу идеясында, бірақ есептеу бойынша Флойд алгоритмінің тиімділігі өте төмен. Флойд алгоритмін қарастырайық. 6 төбесі бар бағытталған граф бар болсын, 12.4-суретте көрсетілген.

12.4-сурет – Бағытталған граф
Осы графтың сыбайлас матрицасы 12.5-кестесінде көрсетілген:
12.5-кесте –12.4-суреттегі графтың сыбайлас матрицасы

Флойд алгоритмінің идеясы бойынша әрбір a[i,j] – төбелер жұбына k (0 – 5) төбелерінің барлық мүмкін нұсқалары мына түрде тексеріледі: a[i,j]>a[i,k]+a[k,j].

Егер a[i,j] жолы үлкен болса, онда сыбайлас матрицада i және j төбелерінің арасындағы жолдың мәні a[i,k]+a[k,j] жолына тең жаңа мәнмен ауыстырылады. Сонымен, ең қысқа қашықтықты анықтайтын матрица дайын болды.

Мысалы, сыбайлас матрицада 2-шіден 1-г дейін жол 8-ге тең. Бірақ, егер біз бірінші 0-ге, ал содан кейін 1-ге орын ауыстыратын болсақ, онда жол 6-ға тең болады: a[2,0]+a[0,1]= 3+3=6. Барлық нұсқаларды тексере отырып, біз мынаны байқадық: 2-5-1 жолы қысқарық, a[2,5]+a[5,1]=2+2=4.

Сонымен, 2-ші мен 1-ші төбелердің арасындағы ең қысқа жол табылды.

Бағдарлама коды:

using System;

using System.Collections.Generic;

using System.Text;

namespace ConsoleApplication1

{

class Program

static void Main()

{

int[,] a = new int[6, 6]

{1000,0,4,7,1000,4},

{3,8,0,5,1000,2},

{1000,6,1000,0,3,1000},

{7,1000,1,4,0,4},

{5,2,1000,1000,2,0}};

int i, j, w, n, k;

Console.WriteLine("Matrizani shigary: ");

for (i = 0; i < 6; i++)

{

for (j = 0; j < 6; j++)

Console.WriteLine();

}

Console.WriteLine();

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("Zhana matrizani shigary: ");

for (i = 0; i < 6; i++)

{

for (j = 0; j < 6; j++)

Console.WriteLine();

}

Console.ReadLine();

}

}

Matrizani shigary:

0 3 1000 3 6 1000

1000 0 4 7 1000 4

3 8 0 5 1000 2

1000 6 1000 0 3 1000

7 1000 1 4 0 4

5 2 1000 1000 2 0

0 3 7 3 6 7

7 0 4 7 6 4

3 4 0 5 4 2

7 6 4 0 3 6

4 5 1 4 0 3

5 2 3 6 2 0
Бағдарламаның (алгоритмнің) кемшіліктері:

– ең қысқы арақышықтықтың маршруты анықталмайды;

– алгоритмнің есептеу тиімділігі n-нің 3-ші дәрежесіне пропорционал (мұнда n – граф төбелерінің саны), ол n-нің үлкен мәндерінде тиімсіз болып келеді.