15 lines
2.7 KiB
Markdown
15 lines
2.7 KiB
Markdown
В случае классической задачи, поиска пути минимальной длины между двумя вершинами графа, мы поддерживаем в каждой посещенной алгоритмом вершине графа минимальную длину пути до этой вершины.
|
||
Здесь стоит оговориться, что будем именовать множество **X** посещенными вершинами, а **V - X** - часть графа, для которой еще нужно найти величину пути или узкого места.
|
||
|
||
В отличии от классического алгоритма, решение этой задачи должно поддерживать величину актуального узкого места пути, приводящего в вершину **v ∈ X**.
|
||
А при добавлении новой вершины из **V - X**, мы должны смотреть не увеличивает ли ребро **(v,u_1)** величину узкого места пути, которое теперь приводит в **u_1**.
|
||
Если ребро **(v, u_1)** увеличивает узкое место, то лучше рассмотреть вершину **u_2**, ребро **(v, u_2)** до которой легче **(v,u_1)**.
|
||
Поиск неувеличивающих узкое место ребёр нужно осуществлять не только среди соседей определенного узла **v**, но и среди всех **v ∈ X**, поскольку отдавая предпочтение вершине, путь в которую имеет наименьшее узкое место в данный момент, мы гарантируем, что мы не ухудшаем ситуацию для других вершин.
|
||
|
||
В результате разбора выше, предлагается руководствоваться следующей формулой при выборе очередной вершины из непосещенных и обновлении величин, которые мы поддерживаем:
|
||
|
||
|
||
|
||
Стоит пояснить, что поиск по **v ∈ X** осуществляется, только для существующих связей **(v,u)**, а **w(v,u)** - это вес ребра **(v,u)**.
|
||
|
||
Очевидно, что сложность такого алгоритма такая же, как и у классического алгоритма Дейкстры. При использовании кучи - **O(m*log(n))**.
|