인접 목록을 사용하는 Floyd Warshall

Question

인접 목록을 사용하여 Floyd Warshall을 코딩 할 수 있습니까? 텍스트 파일에서 백만 개의 꼭지점을 처리해야하므로 인접 행렬은 해결책이 아닙니다. 구현이 이미 가능합니까? 도와주세요.

Answer 1

Floyd Warshall을 인접 목록으로 사용할 수 없으므로 새로운 가장자리가 만들어 지므로 플로이드 Warshall을 인접 목록으로 사용할 수 없습니다.

예 :

먼저 그래프에 2 개의 가장자리 (1-2, 2-3)가 있습니다. 따라서 인접 행렬을 초기화하십시오.

adj [1] [2] = 1; (1과 2 사이의 모서리를 가짐)

adj [2] [3] = 1; (3과 2 사이의 모서리를 가짐)

adj [1] [3] = + oo; (1과 3 사이의 모서리 없음을 의미)

FW가 작동하면 가장자리 1 ~ 2가 추가되기 때문에 가장자리 1 ~ 3이 추가됩니다. < adj [1] [3] = > adj [1] [3] = 2 (1에서 3 사이의 모서리를 가짐을 의미);

당신의 그래프와 제한 시간에서 얼마나 많은 엣지를 풀어야할지 모르지만 그래프의 모든 쌍 사이의 최단 경로를 계산해야한다면 V | 복잡성을 갖는 우선 순위 대기열을 갖는 Dijkstra는 | V | * max (| V | log | V |, | E |)는 Floyd Warshall의 V |^3보다 낫습니다.

Answer 2

Floyd Warshall Implementation using adjacency list 그러나 내부적으로 algo를 검색하기 전에 인접성 목록을 매트릭스로 변환합니다. 그래프가 희소하지 않은 경우 행렬 대신 보조 목록을 사용하면 도움이되지 않습니다. 어쨌든 모든 가장자리를 스캔해야하기 때문입니다. 그러나 그래프가 매우 드문 경우 Floyd Warshall을 사용하는 대신 각 노드에서 Dijkstra'a 최단 경로 알고리즘을 실행하는 것이 좋습니다. Anh Huynh가 다른 응답에서 언급했듯이, 당신이 확실히 | E | ~ | V | 로그^k | V | 0 < = k이면 각 노드에 대해 Dijkstra의 알고리즘을 실행하면 Floyd Warshall보다 더 복잡한 시간을 얻을 수 있습니다.