주어진 두 노드/정점 사이의 경로에서 가장 큰 에지를 찾으려면

Question

MST에서 새 정점을 추가하여 MST를 업데이트하려고합니다. 이를 위해 Chin과 Houck의 "스패닝 트리 업데이트"를 따라 왔습니다. http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf

두 개의 정점 사이의 경로/경로에서 가장 큰 가장자리를 찾으려면 단계가 필요합니다. 내 생각은 꼭지점 사이의 모든 가능한 경로를 찾은 다음 경로에서 가장 큰 가장자리를 찾습니다. 나는 이것을 MATLAB에서 구현하려고 노력 해왔다. 그러나 지금까지 나는 실패했다. 두 개의 꼭지점 사이의 모든 경로 또는 두 개의 지정된 노드/꼭짓점 사이의 경로에서 가장 큰 엣지까지 찾는 모든 리드/클리어 알고리즘이 정말 환영받을 것입니다.

예를 들어 설명 드리겠습니다. 그래프 에지 1-2, 1-3, 2-4과 3-4, 4 및 4 사이의 경로가있는 경우 다음이다 :

1) 4-2-1-3-4

2)

4-3-1-2-4는 새로운 MST에서 큰 가장자리를 제외 할 t 값을 낮춤으로써 당신에게

Answer 1

알고리즘이 작동 감사드립니다. 알고리즘이 완료되면, t는 MST를 완료하기 위해 삽입 될 최하위 에지가됩니다.

m 값은 r에서 z까지의 경로에서 가장 큰 가장자리를 나타내며 각 INSERT 실행에 국한됩니다. 가능한 경우 루프의 각 반복에서 m을 낮추어 이전 m 에지를 t에 대한 가능한 후보로 제거합니다.

단어로 설명하기 쉽지 않지만 단계가 명확해질 때까지 종이에 알고리즘을 실행하는 것이 좋습니다. http://jacob.midtgaard-olesen.dk/?p=140

그러나 새로운 노드 Z와 이전의 다른 노드 사이에 추가 할 수있는 작은 가장자리를 발견하지 않는 한 기본적으로, 알고리즘은 기존의 MST에서 가장자리를 추가합니다

는 여기 단계 스케치하는 빠른 시도를 MST. 이 예에서 B에 대한 더 나은 연결이 알고리즘에 의해 발견되었으므로 가장자리 (A, B)는 새 트리에 없습니다.

참고 t와 (R, W는) 동일한 에지 값이있는 경우, 당신이

(R, W) 마지막으로 당신은 아마 가야 선택 알고리즘 다음과 같은 증거 물마루한다고 생각 선택 H와 K,에 알고리즘이 작동하는 이유를 이해해야합니다. (나는 그것을 전부 읽지 않았다 :))