Как бы я оптимально решал проблему теории графов, когда вес края меняется на любой другой или даже третий прыжок? Могу ли я использовать какой-то модифицированный алгоритм Дейкстры?Кратчайший путь с краевым весом удваивается на каждом другом хопе
Вы можете построить новый график, который кодирует изменяющиеся затраты (хотя, практически говоря, лучше не строить новый график явно).
Учитывая график как
1
A --> B
| /|
2 | /5 | 4
v < v
C <-- D
3
каждая вершина порождает две вершины, а каждая дуга приводит к двум дугам. Дуги идут от оригинала до копии с оригинальным весом и от копии до оригинала при двойном весе.
1 5 3
A ---> B' B ---> C' D ---> C'
2 10 6
A' ---> B B' ---> C D' ---> C
2 4
A ---> C' B ---> D'
4 8
A' ---> C B' ---> D
Теперь поиск из источника или его копии в зависимости от того, в два раза первый хмель, ищет самый дешевый путь к месту назначения или его копии.
Будет ли это работать только для каждого другого веса кромки в два раза? Или он может быть изменен и применен для каждого n-го прыжка в два раза? Например, каждый третий прыжок, или четвертый прыжок? Вы могли бы это сделать, добавив еще один график сверху? Я думаю, что это имеет смысл. Спасибо огромное! – Sauhaarda
@Sauhaarda Общая идея заключается в том, что с учетом графика (V, A), где каждый k-й прыжок должен быть удвоен, постройте новый граф с вершинами V x {0, ..., k-1} и дугами {(v, j) -> (w, (j + 1) mod k) | v -> w в A и j в {0, ..., k-1}}, где вес (v, j) -> (w, (j + 1) mod k) равен 2x веса (v, w) если j = <все, что вам нужно> else 1x. –
I + 1ed ваш пост, но поскольку у меня очень мало репутации, эффекта не было. – Sauhaarda