Намерете най-краткия път между две точки на графика с алгоритъма на Дейкстра

Намирането на най-краткия път между две точки на графика е често срещан проблем в структурите на данни, особено когато се занимава с оптимизация.

Графиката е поредица от възли, свързани с ръбове. Графиките могат да бъдат претеглени (ръбовете носят стойности) и насочени (ръбовете имат посока).

Някои приложения за това са оптимизация на траекторията на полета или 6 градуса на Кевин Бейкън.

Алгоритъм на Дейкстра

Най-честото решение за този проблем е алгоритъмът на Dijkstra, който актуализира най-краткия път между текущия възел и всички негови съседи.

След актуализиране на разстоянието на всички съседи той се придвижва до възела с най-ниското разстояние и повтаря процеса с всички непосетени съседи. Този процес продължава, докато не бъде посетена цялата графика.

Изображение на нивата на кода

Стъпка 0:

Нашата графика трябва да бъде настроена, за да можем да запишем необходимите стойности. На всеки ръб имаме разстоянието между двата възела, които той свързва. Във всеки възел имаме най-краткото разстояние от началния възел.

Нека зададем стойността на всеки възел на положителна безкрайност и зададем стойността на началния възел на нула.

Етап 1:

Погледнете всички възли, непосредствено съседни на началния възел. Стойностите, носени от ръбовете, свързващи старта и тези съседни възли, са най-късите разстояния до всеки съответен възел.

Запишете тези разстояния на възела - презаписване безкрайност - и също така зачеркнете възлите, което означава, че е намерен най-краткият им път.

Стъпка 2:

Изберете един от възлите, който е изчислил най-краткия си път, ние ще наречем това наше пивотно. Погледнете възлите в съседство с него (ще ги наречем нашите възли) и разстоянията, които ги разделят.

За всеки дестинационен възел:

  • Ако стойността в осевата част плюс стойността на ръба, която го свързва, възлиза на по-малко от стойността на целевия възел, актуализирайте стойността му, тъй като е намерен нов по-кратък път
  • Ако всички маршрути до този дестинационен възел са проучени, той може да бъде зачеркнат.

Стъпка 3:

Повторете стъпка 2, докато всички възли не бъдат зачеркнати. Сега имаме графика, където стойностите, които се държат във всеки възел, ще бъдат най-краткото разстояние до него от началния възел.

Повече информация:

Повече за алгоритъма на Дейкстра

Други алгоритми с най-кратък път