Самый легкий круг в ориентированном графе, проходящий через определенную вершину
Я направил график G(V,E) с весовой функцией w. так что вес каждого (u,v) является положительным значением. Мне нужно найти самый легкий круг в графе, в котором вершина k'является его частью.
Я также дал алгоритм, который я могу использовать, который может найти самый легкий путь для графа с положительными весами (я могу использовать его только один раз).
Я думал о создании подграфа G', где все вершины и ребра являются сильно связанными компонентами. найти график, который k'является его частью. затем найдите самый легкий смежный край от k'до некоторого v вершин. из этого vi можно запустить заданный алгоритм и найти легкий путь, а затем добавить вес отсутствующей вершины ( (k',v)).
это кажется правильным? Я в начале этого курса, и я чувствую, что я еще не там.
3 ответа
Я не могу представить, почему вы назвали свою исходную вершину k '. Тем не мение...
Добавьте новый vetrex w, который имеет те же исходящие ребра, что и k '.
Затем используйте алгоритм Дейкстры, чтобы найти кратчайший путь от w до k '.
Замените k ' на w в пути, и у вас будет самый маленький цикл, включая k'.
Это проблема кратчайшего пути из одного источника, где вы исключаете k->k Самостоятельная петля как решение, и найти более длинный путь от k до k. Хитрость всегда заключается в расширении потока по кратчайшему пути.
Учитывая это определение, вы можете начать поиск в Google...
Очень интересная проблема. Я предполагаю, что в графе нет отрицательных значений, или в противном случае для следующих решений требуется сначала нормализовать вершины так, чтобы отрицательные значения стали как минимум 0. Первый метод (тривиальный) состоит в обнаружении всех циклов, начиная с целевой вершины (k). Затем вычислите вес всех этих циклов и возьмите минимум. Второй способ - запустить алгоритм Дейкстры (снова следить за отрицательными весами) с целевого узла (k). Затем выполните итерацию по всем входящим ребрам (k) и выберите исходный узел с минимальным значением Дейкстры. Теперь самый легкий цикл включает в себя единственный путь (образованный обходом Дейкстры) от (k) до выбранного узла + мост, чтобы вернуться к (k). Надеюсь, это поможет:)