입니다. 숙제 문제입니다. 교수님 말씀대로 이해가되지 않으므로이 질문에 대한 답변을 찾는 데 필요한 정보를 어디서 찾을 지 알 필요조차 없습니다. 이 문제를 해결할 방법뿐만 아니라이 물건에 대해 배울 점에 대해 나에게 몇 가지 단서를 줄 수 있다면 감사 할 것입니다.노드 사이의 최단 경로 찾기와 그래프 연결 여부는 분명히 아래의
다음 그래프에서 두 노드 사이의 최단 경로를 찾으십시오 - 선택 사항이지만 문제를 재미있게 만드십시오.
연결된 그래프입니까?
를 사용하여 연결하는 경우에 당신이 말할 수 http://en.wikipedia.org/wiki/A_star
. 그것이 당신에게 달렸다면, 가중치가있는 가장자리를 표현하는 가장 간단한 방법 인 2 차원 배열을 사용할 수 있습니다.
가장 짧은 경로 알고리즘을 구현하는 가장 쉬운 방법은 아마도 Aj보다 약간 느리지 만 복잡하지 않은 Djikstra 일 것입니다. Djikastra를 사용하려면 먼저 우선 순위 대기열을 구현해야합니다. Java에는 PriorityQueue 클래스가 있거나 그렇지 않으면 직접 구현해야합니다. 그런 다음 구현은 Wikipedia 또는 다른 곳에서 사용 가능한 의사 코드를 사용하여 상당히 간단해야합니다.
당신은 두 노드 사이의 최단 경로를 찾는 스타 알고리즘을 사용한다. 그래프가 메모리에 표시되는 방법을 알고 먼저 바람직 할 것 멩거의 정리 http://en.wikipedia.org/wiki/Menger%27s_theorem
나는 내 노트를 읽을 것입니다. –
@SotiriosDelimanolis 솔직히 말해서, 나는 내 강의 노트가 유용하지 않다. 대부분의 경우 온라인 필자는 온라인 자습서 나 YouTube 비디오를 사용하여 내 노트에서 주제를 확장합니다. 대부분의 경우 강의 내용 중 강사가 말한 내용을 요약 한 것입니다. –
또한'graph shortest path'에 대한 구글과 검색 결과의 일부를 읽으십시오. –