비순환 방향없는 연결이 끊어진 그래프의 단일 최단 경로

Question

시작 (v) 및 끝 (u)이 주어진 에지 세트를 통과하는 최단 경로를 찾도록 그래프 알고리즘이 있습니까? 단절 된 버텍스 인 경우, 또한 u가 더 이상 연결이 끊어지지 않을 때까지 누락 된 모서리를 추가하는 최단 경로를 결정합니다.

나는 행이 255 (검정)와 0 (흰색)으로 이루어진 픽셀 행렬을 가지고 있습니다. lines (255)는 break 나 spurs를 가질 수 있고 나는 둘다 제거해야한다. 검은 색 픽셀 7 개 또는 그 이상의 나무로 된 픽셀 매트릭스 포레스트를 가질 수 있습니다. 각 트리의 진정한 끝점을 찾고, 각 트리의 단일 최단 경로를 찾은 다음 모든 비뚤림 나무를 함께 결합하여 단일 한 줄 (즉, 원래 행렬의 가장 먼 두 끝점에서 하나의 최단 경로)을 형성해야합니다. . 모든 에지 가중치는 Dijkstra's algorithm 실행에 대한 1

감사

Answer 1

방법을 고려하고 분리하는 경우, V와 U를 연결 할 수 있을까? "누락 된 모서리를 추가하는 가장 좋은 장소"에 대한 기준은 무엇입니까? 가장자리에는 거리와 같은 가중치가 있습니까?

편집 : "최고의 장소"에 대한 한 가지 아이디어로 모든 연결된 쌍 사이의 최단 경로가 최소가되는 경로를 시도 할 수 있습니다. Floyd–Warshall algorithm은 모든 쌍 사이의 최단 경로를 찾는 데 사용할 수 있습니다. 그래서 v의 트리와 u에있는 각 노드에 대해 Floyd-Warshall을 실행하십시오.

Answer 2

연결이 끊어진 그래프에 대한 문제점이 잘 정의되어 있지 않습니다. 나는 언제나 v와 u 사이를 더할 수있다.

실제로 포레스트라고 불리는 비순환적이고 단절된 연결이 끊긴 그래프가 주어진다면 서브 그래프로 가장자리의 서브 세트가 주어 지므로,이 문제는 사소한 것이므로 사소한 것보다 가장 짧은 경로를 찾을 수 있습니까? 경로 전체 그래프에서 한 경로 만 있습니다.

이것이 일반적인 그래프 G이고 포리 스트 하위 그래프 G '에 대해 이야기하는 경우 자세한 정보가 필요합니다. 이것은 가중치가 있습니까? 그것은 단지 양의 가중치입니까? 가중치가 적용되지 않은 경우 Dijksta의 변형을 수행하십시오. 트리의 지름을 두 리프 사이의 가장 긴 경로의 길이로 정의하십시오 (트리에서 잘 정의되어 있으므로이 경로는 하나뿐입니다). S를 G '의 모든 나무의 지름의 합으로하고, G'에서 모든 가장자리를 2S로 가중치를 설정하면, Dijkstra의 알고리즘은 자동으로 G '를 통해 단계를 선호합니다. G '를 걷는 것이 항상 더 저렴하기 때문에 선택해야합니다.