Графтар 2. Графтар теориясының негізгі анықтамалары

 

 

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] 

  {{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}}; 

  int i, j, w, n, k; 

  Console.WriteLine("Matrizani shigary: "); 

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

  { 

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

   Console.Write("\t" + a[i, j]); 

  Console.WriteLine(); 

  } 

  Console.WriteLine(); 

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

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

  { 

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

   Console.Write("\t" + a[i, 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 

 

Zhana matrizani shigary: 

 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-нің үлкен мәндерінде тиімсіз болып келеді. 

 

жүктеу/скачать 332,21 Kb.

Достарыңызбен бөлісу: