История про Форд-Беллмана появилась из ДЗ по алгоритмам 1-го курса. Кстати, 1-курсники в своих вариантах распределились примерно также.
* Форд-Беллман — алгоритм для орграфов. Для неорграфов с отрицательными рёбрами не работает. Если попытаться его применить к неорграфу, неорребро нужно заменить на два орребра, оно даст отрицательный цикл...
* Решать за полином умеют. Сводят к паросочетанию минимальной стоимости в произвольном графе.
http://acm.math.spbu.ru/~sk1/download/papers/short_path.pdf
(статья скачана отсюда, вк считает её вирусом)
http://people.math.sfu.ca/~goddyn/Courses/800/Resources/GraphMisc/short_path.pdf
* UPD: Если в графе есть отрицательные циклы, задача поиска простого пути NP-трудна (раздвоим вершины, сведём гамильтонов путь).
* Форд-Беллман — алгоритм для орграфов. Для неорграфов с отрицательными рёбрами не работает. Если попытаться его применить к неорграфу, неорребро нужно заменить на два орребра, оно даст отрицательный цикл...
* Решать за полином умеют. Сводят к паросочетанию минимальной стоимости в произвольном графе.
http://acm.math.spbu.ru/~sk1/download/papers/short_path.pdf
(статья скачана отсюда, вк считает её вирусом)
http://people.math.sfu.ca/~goddyn/Courses/800/Resources/GraphMisc/short_path.pdf
* UPD: Если в графе есть отрицательные циклы, задача поиска простого пути NP-трудна (раздвоим вершины, сведём гамильтонов путь).
The story of the Ford-Bellman appeared from the DZ on the algorithms of the 1st course. By the way, the 1-course students in their options were distributed in approximately the same way.
* Ford Bellman - algorithm for digraphs. For non-graphs with negative edges does not work. If you try to apply it to non-graph, you need to replace the neorrebro with two orrebras, it will give a negative cycle ...
* Solve for polynomial able. Reduced to the matching of the minimum value in an arbitrary graph.
http://acm.math.spbu.ru/~sk1/download/papers/short_path.pdf
(article downloaded from here, VC considers it a virus)
http://people.math.sfu.ca/~goddyn/Courses/800/Resources/GraphMisc/short_path.pdf
* UPD: If there are negative cycles in the graph, the task of finding a simple path is NP-hard (split the vertices, we reduce the Hamiltonian path).
* Ford Bellman - algorithm for digraphs. For non-graphs with negative edges does not work. If you try to apply it to non-graph, you need to replace the neorrebro with two orrebras, it will give a negative cycle ...
* Solve for polynomial able. Reduced to the matching of the minimum value in an arbitrary graph.
http://acm.math.spbu.ru/~sk1/download/papers/short_path.pdf
(article downloaded from here, VC considers it a virus)
http://people.math.sfu.ca/~goddyn/Courses/800/Resources/GraphMisc/short_path.pdf
* UPD: If there are negative cycles in the graph, the task of finding a simple path is NP-hard (split the vertices, we reduce the Hamiltonian path).
У записи 14 лайков,
0 репостов,
3506 просмотров.
0 репостов,
3506 просмотров.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
