저는 weight function w를 가진 그래프 G (V, E)를 지시했습니다. 각 (u, v)의 가중치는 양의 값이됩니다. 그래프에서 꼭지점 k '의 일부인 가장 가벼운 원을 찾아야합니다.특정 꼭지점을 통과하는 방향성 그래프에서 가장 가벼운 원입니다.
포지티브 가중치가있는 그래프에 대해 가장 가벼운 경로를 찾을 수있는 알고리즘을 제공했습니다 (한 번만 사용할 수 있음).
강하게 연결된 구성 요소 인 모든 꼭지점과 가장자리가있는 하위 그래프 G '를 만드는 방법에 대해 생각했습니다. k '가 그것의 일부인 그래프를 찾으십시오. k '에서부터 v의 꼭지점까지 가장 가벼운 인접한 가장자리를 찾으십시오. 그에서 v 주어진 알고리즘을 실행하고 경량 경로를 찾은 다음 누락 된 정점의 가중치 ((k ', v))를 더할 수 있습니다.
맞나요? 나는이 과정의 시작 단계에 있으며 나는 아직 거기에 없다고 생각한다.
... 인터넷 검색을 시작할 수 있습니다이 정의를 감안할 때. 어쨌든 ...
은 K ' 같은 나가는 가장자리가 승 새로운 vetrex 를 추가합니다. 그런 다음 에 K ' 승 에서 가장 짧은 경로를 찾기 위해 다 익스트라의 알고리즘을 사용합니다.대체 K '경로에w 에 대한, 당신은 K를 포함하여 최소의주기를 가지고'.
이것은 단일 소스 최단 경로 문제입니다. 여기서 k->k 자체 루프를 솔루션으로 제외하고 k에서 k까지 더 긴 경로를 찾습니다. 트릭은 항상 최단 경로 스레드를 확장합니다.
매우 흥미로운 문제입니다. 그래프에 음수 값이 없다고 가정합니다. 그렇지 않으면 다음 솔루션은 음수 값이 최소 0이되도록 꼭지점을 먼저 정규화해야합니다. 첫 번째 방법 (사소한)은 대상 정점 (k). 그런 다음 모든 사이클의 가중치를 계산하고 최소값을 취하십시오. 두 번째 방법은 대상 노드 (k)에서 Dijkstra 알고리즘 (다시 음의 가중치를 관찰)을 실행하는 것입니다. 그런 다음 (k)의 모든 들어오는 가장자리에 대해 반복하고 최소 Dijkstra 값을 갖는 소스 노드를 선택하십시오. 이제 가장 가벼운 사이클은 (k)에서 선택된 노드 + 다리 (k)로 돌아 오기 위해 (Dijkstra traversal에 의해 형성된) 단일 경로를 포함합니다. 나는 그것이 도움이되기를 바랍니다 :)