Matlab 그래프 이론 점근 복잡성

Question

최근에 그래프 이론에 관심을 갖기 시작했으며 MATLAB 용 생물 정보 도구 도구 상자에 투자 한 후 graphshortestpath 함수가 매우 유용하다는 것을 알게되었습니다. 그러나 함수를 사용할 때 런타임 우선은 함수를 폭 넓은 우선 검색, Dijkstra 알고리즘 또는 Bellman Ford 알고리즘으로 설정했는지 여부와 항상 매우 유사합니다. 수 백에서 수십만에 이르는 다양한 양의 노드로 시도했지만 실행 시간은 거의 동일합니다.

이제 Dijkstra 알고리즘은 MATLAB 웹 사이트의 graphshortestpath 페이지에서 다른 두 알고리즘보다 훨씬 빠른 시간 복잡성을 보여줍니다.

시간 복잡도는 최악의 경우이지만, 실행 시간에 약간의 차이가있을 것으로 예상됩니다.

여기 참조 (http://www.mathworks.co.uk/help/bioinfo/ref/graphshortestpath.html)

오전 여기 뭔가 빠진?

도움을 주시면 감사하겠습니다.

Answer 1

성능을 측정하는 방법에 따라 그래프 경로를 실제로 그리는 데 많은 시간을 소비 할 수 있습니다. 실제 검색보다 비용이 많이들 것입니다.

비교하기 전에 드로잉 프로세스를 제외하는 타이밍 메트릭스를 추가하십시오. 물론, 여러분의 의존성은 꼭지점 수뿐만 아니라 그래프의 가장자리 수에 달려 있습니다.