[Математика] Алгоритм Дейкстры поиска кратчайшего пути в графе на примере телепортов Lineage2

[C2H5OH]

AutoIt: 3.3.8.1

Категория: Математика, Разное

Описание: Вот вы решили поиграть немного в Lineage 2. Прокачались, выполнили квест на вторую профессиию и тут вам сразу же говрят: шара кончилась, телепорты между городами теперь платные.
И что ж мы имеем? Есть населённые пункты в которых находятся телепорты. Но из каждого населённого пункта можно попасть не во все, а только в некоторые. То есть имеем обычный связный граф, в котором узлы соединены не каждый с каждым. Стоимость каждого телепорта легко найти на многочисленных сайтах по Lineage 2.
И теперь мы решаем классическую задачу поиска кратчайшего пути в графе.
Код писался на скорую руку, при желании каждый может разобраться в алгоритме и переписать.
(Стоимость тп просмотрел по диагонали. Вроде бы правильно. Досконально не проверял.)

Код:

Спойлер

#include <Array.au3>
#include <GUIConstantsEx.au3>

; список названий населённых пунктов
Global $nodesNames[17] = ["Town of Gludio","Town of Dion","Town of Giran","Town of Aden","Town of Oren","Town of Goddard","Town of Schuttgart","Rune Township","Gludin Village","Hunters Village","Ivory Tower","Heine","Dark Elf Village","Dwarven Village","Elven Village","Orc Village","Talking Island Village"]

; список названий локаций в окрестностях населённых пунктов
Global $satteliteNames[17] = ["Ruins of Agony"&@CR&"Ruins of Despair"&@CR&"The Ant Nest"&@CR&"Windawood Manor", _
							  "Cruma Marshlands"&@CR&"Cruma Tower"&@CR&"Fortress of Resistance"&@CR&"Plains of Dion"&@CR&"Bee Hive"&@CR&"Tanor Canyon", _
							  "Hardins Private Academy"&@CR&"Dragon Valley"&@CR&"Anthara's Lair"&@CR&"Devil's Isle"&@CR&"Breka's Stronghold", _
							  "Coliseum"&@CR&"Forsaken Plains"&@CR&"Seal of Shilen"&@CR&"Forest of Mirrors"&@CR&"Blazing Swamp"&@CR&"Fields of Massacre"&@CR&"Ancient Battleground"&@CR&"Silent Valley"&@CR&"Tower of Insolence", _
							  "Hardins Private Academy"&@CR&"Skyshadow Meadow"&@CR&"Plains of Lizardmen"&@CR&"Outlaw Forest"&@CR&"Sea of Spores", _
							  "Varka Silenos Stronghold"&@CR&"Ketra Orc Outpost"&@CR&"Hot Springs"&@CR&"Wall of Argos"&@CR&"Monastery of Silence", _
							  "Den of Evil"&@CR&"Plunderous Plains"&@CR&"Frozen Labyrinth"&@CR&"Crypts of Disgrace"&@CR&"Pavel Ruins", _
							  "Wild Beast Pastures"&@CR&"Valley of Saints"&@CR&"Forest of the Dead"&@CR&"Swamp of Screams"&@CR&"Monastery of Silence", _
							  "Langk Lizardman Dwelling"&@CR&"Windmill Hill"&@CR&"Fellmere Harvesting Grounds"&@CR&"Forgotten Temple"&@CR&"Orc Barracs"&@CR&"Windy Hill"&@CR&"Abandoned Camp"&@CR&"Wastelands"&@CR&"Red Rock Ridge", _
							  "Hardins Private Academy"&@CR&"Enchanted Valley, Southern Region"&@CR&"Enchanted Valley, Northern Region"&@CR&"Forest of Mirrors", _
							  "", _
							  "Field of Silence"&@CR&"Field of Whispers"&@CR&"Alligator Island"&@CR&"Garden of Eva", _
							  "Dark Forest"&@CR&"Swampland"&@CR&"Spider Nest"&@CR&"Neutral Zone", _
							  "Mithril Mines"&@CR&"Eastern Mining Zone (Northeastern Shore)"&@CR&"Western Mining Zone (Central Shore)", _
							  "Elven Forest"&@CR&"Elven Fortress"&@CR&"Neutral Zone", _
							  "Immortal Plateau, Southern Region"&@CR&"Immortal Plateau, Northern Region"&@CR&"Cave of Trials"&@CR&"Frozen Waterfall", _
							  "Elven Ruins"&@CR&"Singing Waterfall"&@CR&"Western Territory of Talking Island (Northern Area)"&@CR&"Obelisk of Victory"]

; ГЛАВНОЕ. матрица стоимости переходов между населёнными пунктами
Global $tpPrice[17][17] = [[0,3400,29000,56000,35000,71000,85000,53000,7300,0,0,47000,10000,32000,9200,23000,0], _
							[3400,0,6800,52000,33000,71000,88000,57000,0,0,0,12000,0,0,0,0,0], _
							[29000,6800,0,13000,9400,63000,87000,59000,0,0,0,7600,0,0,0,0,0], _
							[56000,52000,13000,0,6900,8100,53000,37000,0,5900,0,59000,0,0,0,0,0], _
							[35000,33000,9400,6900,0,37000,59000,10000,0,4100,3700,50000,0,0,0,0,0], _
							[71000,71000,63000,8100,37000,0,10000,10000,0,0,0,83000,0,0,0,0,0], _
							[85000,88000,87000,53000,59000,10000,0,10000,0,0,0,100000,0,4400,0,13000,0], _
							[53000,57000,59000,37000,10000,10000,10000,0,0,0,0,82000,0,0,0,0,0], _
							[7300,0,0,0,0,0,0,0,0,0,0,0,16000,38000,16000,26000,9400], _
							[0,0,0,5900,4100,0,0,0,0,0,0,0,0,0,0,0,0], _
							[0,0,0,12000,4400,0,0,0,0,8200,0,0,0,0,0,0,0], _
							[47000,12000,7600,59000,50000,83000,100000,82000,0,0,0,0,0,0,0,0,0], _
							[10000,0,0,0,0,0,0,0,0,0,0,0,0,22000,0,13000,24000], _
							[32000,0,0,0,0,0,4400,0,0,0,0,0,22000,0,23000,17000,46000], _
							[9200,0,0,0,0,0,0,0,0,0,0,0,0,23000,0,18000,23000], _
							[23000,0,0,0,0,0,13000,0,0,0,0,0,13000,17000,18000,0,35000], _
							[0,0,0,0,0,0,0,0,18000,0,0,0,24000,46000,23000,35000,0]]

Global $nodesCost[17], $nodesBackLink[17], $nodesBackLink_tmp[17]
Global $minIndex, $min, $path

; =========================== GUI ==========================================

$GUI_hwnd = GUICreate("L2 тп навигатор", 350, 450)

$Points = _ArrayToString($nodesNames)

GUICtrlCreateLabel("Выберите пункт отправления" , 10, 10, 320)
$GUI_start_point = GUICtrlCreateCombo($nodesNames, 10, 30)
GUICtrlSetData(-1, $Points, $nodesNames[0])

GUICtrlCreateLabel("Выберите пункт назначения" , 10, 70, 320)
$GUI_end_point = GUICtrlCreateCombo($nodesNames, 10, 90)
GUICtrlSetData(-1, $Points, $nodesNames[0])

$Go_button = GUICtrlCreateButton("Рассчитать", 130, 130, 70)
GUICtrlSetState(-1, $GUI_FOCUS) ; просто так

$resLabel = GUICtrlCreateLabel("", 10, 170, 320, 250)

GUISetState()

; ============================ MAIN =======================================

Do
	$msg = GUIGetMsg()
	If $msg = $Go_button Then
		$start = GUICtrlRead($GUI_start_point)	; читаем название пункта отправления
		$startIndex = _ArraySearch($nodesNames,$start)	; и находим его индекс
		$finish = GUICtrlRead($GUI_end_point)	; читаем название пункта назначения
		$finishIndex = _ArraySearch($nodesNames,$finish)	; и находим его индекс
		For $i = 0 to 16				; инициализация рабочих массивов
			$nodesCost[$i] = 999999999	; nodesCos - стоимость маршрута тп из начальной точки в данную
			$nodesBackLink[$i] = 100	; nodesBackLink - индекс из какого узла мы пришли в этот узел
			$nodesBackLink_tmp[$i] = 100
		Next
		$nodesCost[$startIndex] = 0		; общая стоимость пути в начальной точке равна нулю
		$nodesBackLink[$startIndex] = $startIndex	; в начальную тчку мы попали из начальной точки :)
		While $nodesBackLink[$finishIndex] = 100	; если в конечной точке обратный индекс не константа 100, то мы в конечную точку откуда-то пришли
			For $i=0 To 16
				If $nodesBackLink[$i] < 100 Then	; проверяем все узлы где мы уже побывали
					For $j=0 To 16
						If $tpPrice[$i][$j] > 0 Then	; рассматриваем все узлы куда есть переход из узла $i
							$sum = $nodesCost[$i] + $tpPrice[$i][$j]
							If $nodesCost[$j] > $sum Then	; оцениваем непосещённые узлы
								$nodesCost[$j] = $sum
								$nodesBackLink_tmp[$j] = $i	; и запоминаем откуда мы пришли в этот узел с такой оценкой
							EndIf
						EndIf
					Next
				EndIf
			Next
			$min = 999999999
			For $i=0 To 16
				If $nodesBackLink[$i] <> $nodesBackLink_tmp[$i] Then ; рассматриваем узлы, оценка которых изменилась
					If $nodesCost[$i] < $min Then			; и ищем среди них узел с минимальной оценкой
						$min = $nodesCost[$i]
						$minIndex = $i
					EndIf
				EndIf
			Next
			$nodesBackLink[$minIndex] = $nodesBackLink_tmp[$minIndex]
		WEnd
		$path = ""
		$i = $finishIndex
		Do
			$path = " -> " & $nodesNames[$i] & $path
			$i = $nodesBackLink[$i]
		Until $i = $startIndex
		$path = $nodesNames[$startIndex] & $path

		GUICtrlSetData($resLabel,"Путь из "&$start&" в "&$finish&" : "&@CR&@CR&$path&@CR&@CR&"Цена пути : "&$nodesCost[$finishIndex]&@CR&@CR&"Окрестности "&$finish&" : "&@CR&@CR&$satteliteNames[$finishIndex])
	EndIf
	If $msg = $GUI_EVENT_CLOSE Then Exit
Until 0

GUIDelete($GUI_hwnd)

 

[ivanius]

Ты не против если я займусь расспространением твоей програмки, скачают окло 5к+ пользователей, а скорее всего больше - для классики очень актуально.
С указанием авторства твоего конечно. Цены мне только поменять и убрать лишние города, которых пока нету

 

[C2H5OH]

Скрипт выложен здесь для того чтобы любой мог его брать и пользоваться.
:IL_AutoIt_1:

 

[Rioran]

Спирт, спасибо за классный скрипт =)

Переделал его на рельсы Excel с возможностью автоматически подстраиваться под размер исходных данных, найти можно ЗДЕСЬ.