가중치가있는 무 방향성 그래프에서 모든 에지의 가장 짧은 대체 경로를 찾아야합니다. 즉, egde (a, b)가 있다고 가정합니다. 그래프를 얻은 다음, 직접 경로 (즉, edge (a, b))를 건너 뛰는 veti와 b 사이의 최단 경로를 계산하려고합니다. 다른 경로가 없다면 거리는 무한해야합니다. 나는 그래프의 모든 가장자리에 대해이 작업을 수행 할 것입니다. dijkstras 알고리즘 (대상 정점에 도달했을 때 중단됩니다)을 시도했지만 모든 에지에 대해 개별적으로 경로를 계산하는 데 너무 많은 시간이 걸렸습니다. 특히 대안이없는 경우 경로가 가능합니다 (이 경우 전체 그래프를 통과해야합니다). 이에 대한 다른 대안을 제시 할 수 있습니까?에지 자체가 아니어야 그래프의 가장자리 정점 사이의 최단 경로
Here은 얼마 전에 작성한 dijkstra 구현이며 다음 노드를보다 효율적으로 찾기 위해 stl make_heap을 사용합니다. 구현이 올바를 가능성이 큽니다.
편집 : 실시 예에서 파일로부터 판독 할 때, n 정점의 수이고, m은 에지의 수이다 a 및 b 가장자리 정점은, 방향 a에서 b에 c의 중량이다.
언급 한대로 Nobody으로, 알고리즘을 그대로 유지하려면 가장자리를 제거한 다음 다시 추가해야합니다.
나는 Dijkstra의 알고리즘을 적용하여 처음에는 힙/우선 순위를 길이 2의 모든 경로로 채우는 등 그 가장자리를 사용하지 않는다고 추측합니다. 이렇게하면 결과가 정확히 하나의 가장자리를 포함하는 경로를 제외하게됩니다. 결과는 특정 소스에 대한 모든 것을 얻을 수 있으며 가능한 모든 소스에서이 작업을 반복 할 수 있습니다.
결과가 a-> c-> b로 끝날 수 있다고 생각합니다. 여기서 a-> c는 실제로 a-> b-> c입니다. 아니? 길이 2의 모든 경로를 추가 할 때 a-> b를 사용하지 않도록주의해야합니다. – titus
아 사실. (나는 처음에 실제로 질문을 잘못 읽었을 것이다. 그러나 우리가 단지 그 확인을하면 괜찮다고 생각한다.) –
Dennis Meng에 의해 제안 된 해결책은 내가 생각할 것입니다. 그러나 구현을 더 빠르게 할 수있는 최적화 (사전 처리)가 있습니다.
연결된 구성 요소 (트리)의 집합으로 그래프를 구분합니다. [힌트 : 연결된 구성 요소를 찾기 위해 DFS 사용]. - 노드 u을 가진 tree에있는 쌍 (u, v)에 대한 최단 경로를 찾지 못하면이 (내부) 루프에서 벗어날 수 있습니다.
각 노드와 이에 해당하는 트리 간의 매핑을 유지 관리합니다. -이 구현에 도움이됩니다 단계-1
.....
왜 당신은 간단하게 제거하지 마십시오 그래프에서 "허용되지 않는"에지를 선택하고 Dijkstra 또는 다른 "정상"경로 찾기 알고리즘을 실행하십시오. – Nobody
Dijkstras가 너무 많은 시간을 들여야한다면, 나는 운이 없다고 생각합니다. 현재 알려진 알고리즘이 더 좋다고 생각하지 마십시오. – Egor
dijkstra 구현은 다음 노드를 찾을 때 min 힙을 사용합니까? 아니면 모든 검사를 반복하면됩니까? – titus