Найти кратчайший путь из вершины u в v, проходящий через вершину w?

Question

В ориентированном графе с неотрицательными весами ребер я легко могу найти кратчайший путь от u до v, используя дейкстрыНо есть ли какая-нибудь простая настройка Дейкстры, чтобы я мог найти кратчайший путь от u до v через данную вершину w.Или любые другие алгоритмы предложения?

Answer 1

Найдите кратчайший путь от u до w, затем кратчайший путь от w до v.

Answer 2

1. Найти кратчайший путь от u до w
2. Найти кратчайший путь от w до v

Тогда u-> w-> v - кратчайший путь.

Вы можете сделать это, запустив Dijkstra два раза, но вы также можете применить алгоритм Флойда-Варшалла.

Answer 3

Эта проблема NP-сложная, поэтому поиск решения за полиномиальное время маловероятен. См. этот пост для более подробной информации.

Answer 4

Используя следующий подход, мы можем запустить алгоритм всего один раз:

set v_visisted = false
    Start from w and find shortest path to u
    if v was visited during shortest path search to u, set v_visted = true
    If v is part of shortest path from w->u then
          exit with result ( # the path would be u->v->w->v ) 
       else
           if v_visited= true then we already know values for w->v. We have a solution.
           else save path from w->v and switch u to source and find shortest path to v.

Обратите внимание, что выполнение кратчайшего пути от u до v эффективно продолжает первый запуск алгоритма. Поэтому мы запускаем алгоритм только один раз, отслеживая, посетили ли мы 'v'.

Answer 5

Похоже, что вы нашли w в w, а затем нашли w в v, объединяя оба результата. Будет ли это работать?