Минимальный путь в неориентированном графе с заблокированными и разблокированными ребрами

Question

Учитывая неориентированный график с положительными весами, существует 2 вида ребер: заблокированные края и разблокированные края. Определение, если заданное ребро заблокировано или разблокировано, принимает O (1).

1. При заданных двух вершин з, т и положительное число к = O (1), как можно найти кратчайший путь между сек и т который содержит на mostk закрытые кромки?

2. При заданных двух вершин з, т и положительное число к = O (1), как можно найти кратчайший путь между сек и т который содержит точноk заблокированные края?

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

Answer 1

Вы можете решить обе свои проблемы, взяв k копии графа, скажем G_0, ..., G_k, и модифицируйте каждый граф так, чтобы заблокированный край vw в G_i превратился в ребро от u в G_i до v в G_ {i + 1} и из v в G_i в u в G_ {i + 1}. Затем вы можете сделать кратчайшие пути с одним источником из вашего корня в G_0. Второй запрос решается путем считывания расстояния до цели в G_k, в то время как первый разрешается путем считывания минимального расстояния в любом G_i до цели.