Главное меню
Мы солидарны с Украиной. Узнайте здесь, как можно поддержать Украину.

Ответ

Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.
Ограничения: максимум вложений в сообщении — 3 (3 осталось), максимальный размер всех файлов — 300 КБ, максимальный размер одного файла — 100 КБ
Снимите пометку с вложений, которые необходимо удалить
Перетащите файлы сюда или используйте кнопку для добавления файлов
Вложения и другие параметры
Проверка:
Оставьте это поле пустым:
Наберите символы, которые изображены на картинке
Прослушать / Запросить другое изображение

Наберите символы, которые изображены на картинке:

√36:
ALT+S — отправить
ALT+P — предварительный просмотр

Сообщения в этой теме

Автор RawonaM
 - апреля 22, 2012, 18:16
Нет, все-таки контрпример правильный. Длина пути к В не будет правильной. Но меня смущает
Цитировать
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.

тут мне кажется ошибка. Следущую вершину после В он должен взять С вроде как.
Автор RawonaM
 - апреля 22, 2012, 18:06
http://www.ics.uci.edu/~eppstein/161/960208.html
Цитировать
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
 - апреля 22, 2012, 08:52
Вообще в целом, чтобы найти несколько путей нужно строить транспортную сеть, лучше ничего нет?
Автор RawonaM
 - апреля 22, 2012, 08:47
Дан граф ориентированный или неориентированный с вершинами С, П и гранью Е, известно что есть путь между С и П.
Нужно дать эффективный алгоритм, который определяет, есть ли простой путь от С к П через грань Е.
Я пока ничего не придумал.
Автор RawonaM
 - апреля 21, 2012, 11:11
Дано определение: полусильно связной граф, это ориентированный граф, в котором между вершинами А и В есть путь или в одну сторону или в другую (или в обе).

Помнится мне, что чтобы определить сильную связность можно просто с любой вершины запустить BFS или DFS и потом сделать то же самое для графа, в котором все направления перевернуты. Если в обоих случаях найдутся все вершины, то граф сильно связной.

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

Если с вершины S нашлись некоторые вершины, и потом в обратную сторону нашлись остальные вершины, то очевидно что условие выполняется для пар S с любой другой. Теперь между всеми другими вершинами есть путь через S. С другой стороны, если для S не нашлись все вершины то уже граф не полусильно связной. Верно ли я рассуждаю?
Автор GaLL
 - января 23, 2012, 22:32
Цитата: RawonaM от декабря 16, 2011, 20:46
Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.
Оказывается, до сих пор не придумано ничего лучше, чем решать эту задачу через поиск длин кратчайших путей между всеми парами вершин:
http://arxiv.org/abs/1104.2882
Цитировать
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.
Автор GaLL
 - января 23, 2012, 20:40
Цитата: RawonaM от января 10, 2012, 10:50
Похожий вопрос. Дан граф с весами на гранях, вершины s и t (s≠t) и грань е. Нужно найти эффективные алгоритмы, отвечающие на вопросы:
1) Принадлежит ли е к каждому минимальному пути между s и t.
2) Принадлежит ли е к какому-нибудь простому минимальному пути между s и t.
Если известны длины кратчайших путей от s до всех остальных вершин, то и на первый, и на второй вопрос можно ответить за O(E) не только для какого-то конкретного e, но и для всех рёбер сразу. Для этого можно воспользоваться вспомогательным графом, построенным следующим образом:
Пусть исходный граф - G, а d - длина кратчайшего пути от s до i, а H - пустой граф с тем же числом вершин и без весов у рёбер. Перебираем все рёбра из G, пусть текущее соединяет вершины a и b (из a в b), и его длина - q. Если d = d[a] + q, то добавляем в граф H ребро из a в b.
Далее всё сводится к исследованию графа H. Понятно, что любой путь из a в b в графе H будет соответствовать кратчайшему пути из a в b в графе G.
Автор RawonaM
 - января 12, 2012, 11:33
Цитата: RawonaM от января 12, 2012, 11:15
Цитата: RawonaM от января 10, 2012, 10:50Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.
Нет, что-то это бред какой-то.
Нет, это не бред. Вроде как все правильно.
Автор RawonaM
 - января 12, 2012, 11:15
Цитата: RawonaM от января 10, 2012, 10:50
Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.
Нет, что-то это бред какой-то.
Автор RawonaM
 - января 10, 2012, 10:50
Похожий вопрос. Дан граф с весами на гранях, вершины s и t (s≠t) и грань е. Нужно найти эффективные алгоритмы, отвечающие на вопросы:
1) Принадлежит ли е к каждому минимальному пути между s и t.
2) Принадлежит ли е к какому-нибудь простому минимальному пути между s и t.

Ввиду опыта с минимальными остовами я так сделал:
1) Находим вес минимального пути, убираем е и опять находим вес минимального пути. Если вес изменился, то е принадлежит ко всем минимальным путям.
2) Если есть отрицательные циклы, то нет минимального маршрута.
Иначе находим вес минимального маршрута.
Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.

Верно?