Самый длинный простой контур
Как ответил Дэдпул, вы должны отделить класс MyData от класса @Configurtion.
@Configuration мета-аннотирован с помощью @Component, поэтому, когда вы аннотируете MyData с помощью @Configuration, Spring также связывает его как обычный bean-компонент, и это делает двойное определение bean-компонентов MyData.
2 ответа
alt text http://dl.getdropbox.com/u/317805/path2.jpg
С помощью вашего алгоритма приведенный выше график преобразуется в нижний.
Самый длинный путь - это красная линия на приведенном выше графике. И в зависимости от того, как нарушаются связи и используемого алгоритма, кратчайшим путем на преобразованном графике может быть синяя или красная линия. Таким образом, преобразование весов ребер графа с использованием упомянутой константы не дает значительных результатов. Вот почему вы не можете найти самый длинный путь, используя алгоритмы кратчайшего пути, независимо от того, насколько вы умны. Более простое преобразование могло бы заключаться в том, чтобы отрицать все веса ребер и запускать алгоритм. Я не знаю, ответил ли я на ваш вопрос, но что касается свойства path, преобразованный граф не имеет никакой полезной информации о расстоянии.
Однако это конкретное преобразование полезно в других областях. Например, вы можете заставить алгоритм выбирать определенный вес ребра в сопоставлении бипатрита, если у вас есть более одного ограничения, добавив огромную константу.
- Редактировать: Мне сказали добавить это утверждение: Приведенный выше график не только о физическое расстояние. Им не обязательно соблюдать неравенство треугольника. Спасибо.
Если бы Вы могли бы решить проблемы кратчайшего пути с отрицательными весами, Вы нашли бы самый длинный путь, эти два эквивалентны, это могло быть сделано путем помещения веса-w вместо w
Стандартным алгоритмом для отрицательных весов является Алгоритм Беллмана-Форда. Однако алгоритм не будет работать, если будет цикл в графике, таким образом, что сумма краев отрицательна. В графике, который Вы создаете, все такие циклы имеют отрицательные веса суммы и таким образом, алгоритм не будет работать. Если, конечно, у Вас нет циклов, в этом случае у Вас есть дерево (или лес), и проблема разрешима через динамическое программирование.
Если мы заменяем вес w m-w, который гарантирует, что все веса будут положительны, то кратчайший путь может быть найден с помощью стандартных алгоритмов. Если кратчайший путь P в этом графике имеет k края затем, длина k*m-w (P), где w (P) является длиной пути с исходными весами. Этот путь не обязательно, самый длинный, однако, всех путей с k краями, P является самым длинным.