Мне было интересно, есть ли алгоритм, который найдет кратчайшие пути в графе.кратчайшие пути не путь в графе
Предположим, что у меня есть график, где есть пары путей от одной вершины к другой. Два или более из этих путей имеют одинаковую стоимость. Как я могу отметить, найти и найти все кратчайшие пути между этими вершинами? Насколько я знаю, алгоритмы Дейкстры или Беллмана-Форда найдут самый короткий путь, но они «выбирают» только один.
Алгоритм Дейкстры дает вам стоимость всех возможных промежуточных узлов и стоимость кратчайшего пути к раковине. Вы можете получить все пути из источника, чтобы потопить, выполнив первый поиск глубины с раковины на источник (обращаясь назад), где вы пересекаете край (назад), только если стоимость этого края равна разнице между стоимостью кратчайший путь от источника к двум узлам. Конечно, вы получаете пути в обратном порядке, но их легко изменить.
.
Не могли бы вы привести мне пример? Я не думаю, что правильно это понял. Мне нужно начинать с вершины раковины и делать DFS, понятно, однако я не понимаю условия прохождения края – Berial
Ok Начните с вершины раковины, скажем, ваш самый короткий алгоритм пути говорит, что он находится на расстоянии 20 от источника , Скажем, что есть три вершины, ведущие к раковине, назовите их a, b, c, вызовите сток x. Скажем, что a находится на расстоянии 18 от источника, а кромка имеет вес 2, b - расстояние 17 от источника, а bx имеет вес 4, а c - 19 от источника, а cx - вес 1. Это означает, что есть кратчайший пути от источника к потоку, который заканчивается топором и cx. Используйте эту процедуру, чтобы отобразить все пути, заканчивающиеся на ax, а затем все пути, заканчивающиеся на cx. – deinst
Хорошо, я думаю, что мне удалось написать это :) Я должен проверить свою программу, и я левт. Ты знаешь, все ли в порядке – Berial
Посмотрите на Floyd-Warshall.
В информатике, алгоритм Флойд-Воршалл (иногда известные как ВДИ алгоритм или алгоритма Рой-Флойд) является алгоритмом графа анализа для нахождения кратчайших путей во взвешенном графе (с положительный или отрицательный край веса). Однократное выполнение алгоритма найдет длины (суммированные веса) кратчайших путей между всеми парами вершин, хотя не возвращает данные о самих дорожках . Алгоритм представляет собой пример динамического программирования .
Как это помогает? Вопрос касается всех кратчайших путей между заданными двумя вершинами. Есть только одна пара. – 2010-08-09 17:45:22
@Moron - О, моя ошибка. У меня создалось впечатление, что Бериал говорил, что эти алгоритмы нашли только самые короткие между любыми двумя узлами, а не все одинаково короткие пути между двумя конкретными узлами. Floyd-Warshall найдет все кратчайшие пути на графике, а не все кратчайшие пути между двумя вершинами. –
Найти кратчайший путь. Если есть другие пути одного и того же расстояния, найдите их тоже? –