Цитировать
It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3.
Цитировать
Dijkstra and negative lengths
Dijkstra's algorithm does not work with negative edge weights. For instance, consider the following graph (assume the edges are all directed from left to right):
2
A-----B
\ /
3 \ / -2
C
If we start with A, Dijkstra's algorithm will choose the edge (A,x) minimizing d(A,A)+length(edge), namely (A,B). It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3. But it never finds the shortest path from A to B, via C, with total length 1.
Цитата: RawonaM от декабря 16, 2011, 20:46Оказывается, до сих пор не придумано ничего лучше, чем решать эту задачу через поиск длин кратчайших путей между всеми парами вершин:
Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.
Цитировать
Minimum cycle and APSP. Recently, in FOCS'10 Vassilevska W. and Williams [24] showed that the minimum
weight cycle problem is equivalent to many other graph and matrix problems for which no truly subcubic (O(n3− ε)-
time for constant ε > 0) algorithms are known. They showed that if there is a truly subcubic algorithm for the
minimum weight cycle problem, then many other problems such as the all-pairs-shortest-paths (APSP) problem also
have truly subcubic algorithms. Hence, the minimum weight cycle problem has a pivotal role in understanding the
complexity of many fundamental polynomial problems in a similar spirit to the role of 3SAT for NP-hard problems.
Цитата: RawonaM от января 10, 2012, 10:50Если известны длины кратчайших путей от s до всех остальных вершин, то и на первый, и на второй вопрос можно ответить за O(E) не только для какого-то конкретного e, но и для всех рёбер сразу. Для этого можно воспользоваться вспомогательным графом, построенным следующим образом:
Похожий вопрос. Дан граф с весами на гранях, вершины s и t (s≠t) и грань е. Нужно найти эффективные алгоритмы, отвечающие на вопросы:
1) Принадлежит ли е к каждому минимальному пути между s и t.
2) Принадлежит ли е к какому-нибудь простому минимальному пути между s и t.
Цитата: RawonaM от января 12, 2012, 11:15Нет, это не бред. Вроде как все правильно.Цитата: RawonaM от января 10, 2012, 10:50Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.Нет, что-то это бред какой-то.
Цитата: RawonaM от января 10, 2012, 10:50Нет, что-то это бред какой-то.
Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.
Страница создана за 0.071 сек. Запросов: 23.