Расчет кратчайшего пути между 2 узлами с обязательными точками посередине

Question

Я пытаюсь решить проблему в двунаправленном взвешенном графике , представляющем Metro Service, с примерно 300 узлами и 700 ребрами.

Узлы определяются станцией метро, ​​а ребра - это строки с информацией о линии, к которой они принадлежат, и время (являющееся весом ребра), необходимое для перемещения по этому ребру.

Я должен определить самый быстрый путь между двумя станциями, учитывая список неупорядоченных (если бы им было приказано перестановка кратчайших путей между всеми станциями, было бы достаточно) обязательных станций, и он может пойти через другие станции, а также

После того, как я искал проблему, я увидел несколько предложений по созданию подграфа + применение DFS. Поэтому я создал график с начальной станцией + обязательными станциями + конечной станцией в качестве новых вершин, а ребра с информацией о кратчайшем пути между каждой станцией + время, которое требуется для перемещения.

Проблема, с которой я столкнулся сейчас, заключается в следующем: как применить DFS к этому новому подграфу, который принудительно делает последнюю посещенную станцию ​​той, которая у меня есть, в качестве пункта назначения?

Извините за длинный вопрос!

Answer 1

У меня есть другая идея.Поскольку граф является ациклическим, мы можем разбить обязательный узел (кроме узла источника и назначения) на два узла ( A до A _start и A _end ) и установите ребро между ними и установите вес как -infinity.Весь входящий фронт к обязательному узлу A будет подключен к A _start , а весь исходящий фронт из обязательного узла A будет получен из A _конец .Наконец, мы запустим алгоритм dijkstra для исходного узла к целевому узлу.Поскольку в обязательном узле мы устанавливаем бесконечный вес, dijkstra обязан пройти через них, чтобы минимизировать стоимость.Кроме того, поскольку график является ациклическим, нам не нужно беспокоиться об отрицательном цикле.

Answer 2

Сначала нужно определить что-то для своей проблемы: являются ли обязательные станции только станциями, которые вам нужно посетить, чтобы добраться до пункта назначения?Или есть другие неизвестные станции между ними, которые не являются обязательными, но могут потребоваться в кратчайшем пути?

Предполагая, что этот график содержит циклы:

Если в списке обязательных станций указаны все станции, которые вам понадобятся, чтобы добраться до пункта назначения, это можно решить с помощью алгоритма Дейкстры на подграфе всехобязательные узлы.

В другом случае это было бы более сложно (на самом деле NP-hard). См. этот ответ для более глубокого решения: Кратчайший путь, который пересекает список требуемых ребер