Блог пользователя powqer

Автор powqer, 13 лет назад, По-русски
Дан взвешенный ориентированный граф. Необходимо найти циклы отрицательной длины, а точнее пары вершин, путь между которыми может быть неограниченно мал.
Мое решение:
1)Посчитать расстояния между всеми парами вершин алгоритмом Флойда.(в итоге получим матрицу путей d[i][j])
2)Если для двух вершин v1 и v2 справедливо, что d[v1][v2]+d[v2][v1]<0, то
d[v1][v2]=d[v2][v1]=d[v1][v1]=d[v2][v2]=-INF.
Просьба объяснить что неверно в таком рассуждении и, если это не трудно, привести контрпример.
Заранее спасибо.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Воспользуйся лучше этим алгоритмом http://e-maxx.ru/algo/negative_cycle
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Контрпример:
0 -1 inf inf
-1 0 0 inf
inf 0 0 100
inf inf 100 0
Между 3 и 4 можно сделать сколь угодно маленький путь
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я так понимаю inf значит, что пути нет? Но тогда мы можем сделать такой путь только между 1 и 2. А так с 3 можно попасть либо в 4(за 100), либо во 2 за ноль, а со второй в 4 пути нет. А вот с 4 в 3 есть за 100. Значит, если зациклится, мы можем получить только + INF?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мы можем добраться из третьей вершины во вторую, там сделать стопицот витков между первой и второй, возвратиться во вторую, потом обратно в третью(у нас уже будет отрицательный вес, при том какой захочешь) и в четвертую.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      inf(infinity) всегда означало бесконечность.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Как я понял, в контрпримере приведена была матрица смежности. А что в данном случае значит бесконечность-не понятно.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Она может значить наличие пути, которое полностью все убьет, потому-что inf-x=inf, либо-же очень большое число(скорее всего именно это), но никак не отсутствие пути.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Это неправильно. Допустим, вот такой пример:
4 5
1 2 10000
2 3 -1
3 2 0
3 4 10000
4 1 10000

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот тут вроде понял. У меня алгоритм найдёт только цикл 2-3. А как же тогда мне выяснить, между какими вершинами неограниченно малый путь? Хотелось бы применять именно алгоритм Флойда
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      "Хотелось бы"-не правильный вариант. Правильный вариант-"надо". А какой алгоритм надо применять в этом случае, было написано в первом комментарии.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я с Вами тут не согласен. Если человек изучает алгоритм, то ему будет полезно знать как можно больше задач, на которых можно применить его. Хотя это лично мое мнение.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вот это я и имел ввиду:). А вообще задача вроде как решается с помощью Флойда, и меня интересует именно это решение,а не Форд-Белман или что-то ещё.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Насколько я знаю, стандартное решение этой задачи все-таки Форда-Беллмана. Знание решения Флойдом - это скорее для общего развития.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              На самом деле, если по условию задачи нас спрашивают найти все такие пары вершин (i,j), между которыми путь бесконечно мал, то алгоритм Форда-Беллмана здесь уже будет хуже - его придётся запускать n раз (по крайней мере, я не знаю способа избежать этого).
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Можно одним ФБ найти для каждого цикла вершину которая на нём лежит, найти достижимые по прямым рёбрам и по обратным ну и вот уже и ответ.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

AFAIK, правильно так:

"между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t]<0"

http://e-maxx.ru/algo/floyd_warshall_algorithm

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот это условие мне почему-то непонятно(как раз читал Ваш сайт)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А что именно непонятно? Само условие или почему это так?

      Ещё раз, само условие выглядит так:

      если существует такая t, что

      d[i][t]<INF && d[t][t]<0 && d[t][j]<INF,

      то кратчайший путь (i,j) - бесконечно маленький.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
1) Если вершина t лежит на цикле отр. веса, то d[t][t] будет меньше 0 (можно показать)
2) между вершинами v1 и v2 есть путь сколь угодно малого веса <=> есть вершина t, которая доступна из v1 и из которой доступна v2, т.ч. через t проходит цикл отрицательного веса (т.к. путей, проходящих через каждую вершину не более, чем однажды, конечное число)

1) + 2) = вышеописанный алгоритм