Алгоритъм за намиране на най-дълъг път в граф - Информатика, програмиране
4. Алгоритъм за намиране на най-дългия път в граф
4.1 Математическо описание на проблема и методите за неговото решаване
Графът (G, X) е колекция от две крайни множества: набор от точки, които се наричат върхове (X = 1,…, Хn>), и набор от връзки в двойки върхове, които се наричат дъги или ръбове ((Xi, Xj) Î G) в зависимост от наличието или отсъствието на насоченост на връзката.
Ръбът е име, дадено на две противоположни дъги (Xi, Xj) и (Xj, Xi). На графиката те са изобразени като една линия без стрелка. Ръб или дъга, чиито крайни върхове съвпадат, се нарича цикъл.
Ако на всеки ръб е дадена посока, тогава се казва, че графиката (G, X) е ориентирана. В противен случай графът се нарича неориентиран.
Два върха, които са крайни за някакво ребро или някаква дъга, се наричат съседни. Съответно, тази графика може да бъде представена чрез матрица на съседство или матрица на инцидентност.
Матрицата на инцидентност е правоъгълна матрица с броя на редовете, равен на броя на върховете на графиката, и с броя на колоните, равен на броя на ръбовете (дъгите) на графиката. Елементите на матрицата a се задават, както следва: "1" се задава, ако върхът vi е инцидентен на ръба uj; "0" в противен случай.
Казват, че връх и ръб (дъга) са инцидентни един на друг, ако върхът е крайната точка за този ръб (дъга).
Пътят от началния връх xn до крайния връх xk е последователност от дъги, започващи от върха xn Î X, завършващи във върха xk Î X и така, че краят на следващата дъга е началото на следващата: (хн, хi1) (хi1, хi2) (хi2… хik) (хik, xk) = (xн, хк).
Елементарният път е път, в който върховете не се повтарят.
Простият път е пътят, в който дъгитене се повтарят.
Маршрутът е поредица от ръбове, които, подобно на път, образуват верига.
Дължината на пътя на претеглен граф се определя като сбор от теглата - неговите дъги. Ако графиката не е претеглена, тогава можем да приемем, че теглата на дъгите са равни на 1.
Най-късият път между избрана двойка върхове xn и xk е пътят, който има най-малка дължина сред всички възможни пътища между тези върхове.
При конструирането на най-дългия път се разглеждат елементарни или прости най-дълги пътища, най-дълги пътища с даден брой завършени цикли. Най-дългият път между xn и xk е пътят, който има най-голяма дължина сред всички възможни пътища между тези върхове.
По този начин намирането на най-дългия път е търсене на множеството от върхове, които съставят този път.
Вълновият алгоритъм получи името си поради факта, че самият принцип на неговата работа се основава на "излъчването на вълна", на някакво хипотетично смущение, според резултатите от което е възможно да се прецени броят на върховете, съседни на избрания, както и разстоянието (дължината на дъгата) до всеки от тях.
Очевидно е, че няколко пътя могат да стигнат до всеки връх от върха X, сумите от дължините на дъгите по различните пътища са различни. Когато търсите най-дългия път, трябва да изберете максималната сума. Вълните на разпространение на теглото по различни пътища достигат всеки връх последователно, със следващата вълна или старото тегло на върха трябва да бъде оставено или заменено с ново (по-голямо). Следователно, когато се изчислява теглото на върха X i поради вълната, приближаваща се към него по дъгата (X j, X i), теглото V i се изчислява по формулата V i =max (V i, V j + l ji).
Теглата на върховете по време на разпространението на вълната могат да се променят многократно. С всяка промяна в теглото V i на върха, това увеличение на теглото трябва да се прехвърли към върховете на резултата X i, т.е.необходими са специални средства за отразяване на факта, че даден връх получава ново тегло и го прехвърля към други върхове. Като такъв инструмент се използва масив от номера на върхове, които са получили ново тегло (при всяка промяна на теглото номерът на върха се включва в този масив, ако не е бил там, той се изключва при прехвърляне на теглото).
4.2 Вербално описание на алгоритъма и неговата работа
1. Всички върхове на графа получават тегла V i=0, номерът на върха X n се въвежда в масива M от номерата на върховете, които са променили теглото. Останалите върхове X i не попадат в масива M.
2. Ако масивът M е празен, се изпълнява стъпка 3, в противен случай се избира следващият връх X i с изключение от него и се преизчисляват теглата на върховете, принадлежащи към резултата G (X i) на върха X i:
Ако теглото на V j се промени, тогава числото j се включва с намаляване на харесванията до M. Стъпка 2 се изпълнява отново.
3. Ако тегло , тогава се заключава, че няма път от върха X n до върха X k, в противен случай се изпълнява процедурата за избор на дъги, като се движи в обратен ред, проверяваме дали условието X i – X j = l ij е изпълнено, за входовете на върха X i, ако е изпълнено, тогава се избират върха X j и дъга l ij.
4. След избиране на дъгите се построяват най-дългите пътища, чиито дължини са равни на V k.
При конструирането на най-дългите пътища се вземат предвид елементарни или прости най-дълги пътища, най-дългите пътища с даден брой цикли.
4.3 Структури от данни
От самата структура на алгоритъма е очевидно, че за неговата работа е необходимо:
1. Масив B-масив от дъгови връзки в клетки с номера i, j, които ще бъдат теглото на съответната дъга l ij.
2. Масив M - масив от върхове, които са променили теглото си.
3. Array E - масив, съдържащ стойностите на теглата и състоянията на върховете.
4. Array P - масив, съдържащ избрани дъги.
5. Редица индексни променливи, необходими за преминаване през масиви B, E, P, както и съдържащи индекса на текущия връх, както и редица буферни променливи, необходими за текущи аритметични и циклични операции (всички индекси трябва да са от целочислен тип).