Единственный кратчайший путь ациклического неориентированного несвязного графа

Question

Существует ли алгоритм графа, который с учетом начала (v) и конца (и) найдет кратчайший путь через заданный набор ребер, но если u - несвязная вершина, он также определит кратчайший путь для добавления недостающие края, пока вы больше не отключены?

У меня есть матрица пикселей, где линии состоят из 255 (черный) и 0 (белый). линии (255) могут иметь разрывы или шпоры, и я должен избавиться от обоих. Я мог бы иметь лес матрицы пикселей, скажем, с 7 или около того деревьями черных пикселей. Мне нужно найти истинные конечные точки каждого дерева, найти один кратчайший путь каждого дерева, а затем объединить все наклонные деревья вместе, чтобы сформировать одну единственную линию (т. Е. Один кратчайший путь из самых дальних 2 конечных точек в исходной матрице) , все веса ребер можно считать равными 1.

Спасибо

Answer 1

Как насчет запуска алгоритма Дейкстры и, если он отключен, подключить v и u? Каковы ваши критерии для «лучшего места, чтобы добавить недостающий край?» Имеют ли ребра вес (например, расстояние)?

Редактировать : Для одной идеи «лучшего места» вы можете попробовать путь, который имеет минимальную сумму кратчайших путей между всеми связанными парами. Алгоритм Флойда – Варшалла может использоваться для поиска кратчайших путей между всеми парами. Итак, запустите Floyd-Warshall для каждого узла в дереве v и u.

Answer 2

Ваша проблема плохо определена для отключенных графиков. Я всегда могу добавить и край между v и u.

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

Если это общий граф G, а вы говорите о лесном подграфе G ', тогда нам нужно больше информации. Это взвешено? Это только положительные веса? Если он невзвешенный, сделайте какой-нибудь вариант Дейкста. Определите диаметр дерева, чтобы быть длиной самого длинного пути между двумя листьями (это хорошо определено в дереве, так как там только один такой путь). Пусть S будет суммой диаметров всех деревьев в G ', затем установите вес всех ребер из G' в 2S, тогда алгоритм Дейкстры автоматически предпочтет пройти через G ', выходя за пределы G', только когда нет выбор, так как прогулка через G 'всегда будет дешевле.