5
Google에 계속 노력하고 있지만 결과는 내가 혼란에 빠지기 만하는 것입니다. 그것은 아마도 둘 다 사용할 수있을 것 같습니다? 그렇다면 기본적으로 어떤 용도로 설계되었으며 기본 지향적이지 않은 방식으로 작동하도록 변경해야하는 항목 (방향이 지정되었거나 지정되지 않은 경우)은 무엇입니까?Dijkstra의 방향 또는 무향 그래프 알고리즘입니까?
편집 : 참조를 위해, 나는이 문제를 내가이 (공항) 등의 목록을 주어진 마지막 학기를했다 :
나는 그것이 지시되었다 말하고, 최단 경로를 찾는 질문을 받았다AER,KZN,1.8835
ASF,KZN,1.3005
ASF,MRV,1.1204
CEK,KZN,1.9263
CEK,OVB,1.6733
DME,KZN,1.7892
DME,NBC,2.2319
DME,UUA,2.3786
EGO,KGD,1.4649
EGO,KZN,1.2603
GYD,NBC,2.0755
. Github에서 발견 한 Dijkstra의 알고리즘에 넣어 두었습니다. (오픈 컴퓨터 중기 였기 때문에 처음부터 알고리즘을 작성할 시간이 거의 없었습니다.) 제 교수는 반환 된 최단 경로가 잘못되었다고 말했습니다. 목록이 지시되어야하기 때문에 가능한 경로조차도. 이 수정을 위해 알고리즘이나 목록을 수정해야만하는지 잘 모르겠습니다. 결국 돌아온 두 번째로 짧은 경로는 사실상 가장 짧은 경로 였지만 여전히 문제가 무엇인지 궁금합니다.
내 목록에 각 가장자리에 대해 중복되지만 역전 된 항목이 없으면 지시 된 최단 경로를 제공해야합니까? 내가받은 목록은 지시 받았지만 Dijkstra의 구현을 사용하면 나에게 방향이없는 최단 경로가 부여되었습니다. – Austin
글쎄, 이것은 당신이 발견 한 구현이 무언가가 아닌 방향으로 무언가를 귀하의 목록에있는 항목으로 해석하는 것처럼 들리므로 아마도 알고리즘을 직접 구현해야합니다. 내가 아는 것들은 일반적으로 인접성 목록 (주어진 노드에서 어떤 노드에 도달 할 수 있는지에 대한 정보를 담고있는 목록이다. * => 연결이 지시 됨 *). 이것이 내가 방향이없는 그래프에서 작동하도록 할 필요가 없다고 말한 이유입니다. 그러나 어떤 이유로 든 알고리즘이 연결을 양방향으로 자동 해석하면 변경해야합니다. – Keiwan
@ Keiwan이 게시물은 https://stackoverflow.com/questions/22649416/why-cant-prims-or-kruskals-algorithms-be-used-on-a-directed-graph는 prims 알고리즘이 방향성 그래프에 대해 실패 할 것이라고 말합니다. 따라서 거의 프리믹스 인 Dijkstras는 게시물에서 제시된 예에서도 실패합니다. – WSS