그래프의 지점 간 경로

Question

그래프에서 두 정점 사이의 최적 경로를 찾을 수있는 알고리즘을 원합니다 (양수 int 가중치 포함). 내 그래프가 비교적 큽니다 (최대 100 정점). 나는 dijkstra 알고리즘을 고려해 보았습니다. 그러나 넷을 검색 할 때 대부분의 구현은 내 경우에 100x100이 될 인접 매트릭스를 사용합니다.

특정 소스를 읽고 배우고, 나에게 C++ 구현을 제공하는 것이 좋습니다.

PS : 알고리즘은 두 점 사이의 최단 거리뿐만 아니라 필요한 경로를 출력해야합니다.

감사합니다.

Answer 1

A*을 들여다 보았습니까?

여기 시작하는 좋은 기사의 읽기 : http://www.redblobgames.com/pathfinding/a-star/introduction.html