|
다익스트라 알고리즘을 사용한 서울 지하철 최단경로 탐색 프로그램을 구현한 적이 있었습니다. 사실 그때는 알고리즘의 정확한 개념은 알지 못하고 그냥 위키의 소스를 사용해서 어떻게 구현할 것 인가하는 방법을 택했습니다. 그래서인지
|
|
|
\\n\"
<< \"출발점과 도착점이 같으면 종료합니다.\\n출발점의 번호를 입력하십시오 : \";
cin >> start_node;// 출발점 번호 입력
path[0] = start_node; // 출발점을 path[0] 에 기록
cout << \"도착점의 번호를 입력하십시오 : \";
cin >> end_node;//
|
|
|
경로는 : \");
p = start;
while(true)
{
printf(\"%d => \", p +1);
p = city[p].from;
if (p == finish)
{
printf(\"%d\\n\", p+1);
break;
}
}
return;
}
소스코드
출력결과
4. 다익스트라 알고리즘과 플로이드 알고리즘의 비교
다익스트라 알고리즘은 한 시작점을 잡고 그 시
|
|
|
경로를 말한다.
(2) 최단 경로 문제 : 한 가중치 그래프에서 주어진 두 정점 x와 y를 연결하는 경로 상의 모든 선분들의 가중치 합이 최소인 성질을 갖는 경로를 찾는 것이다.
(3) 최단 경로 기법 :
➀ 그리디(Greedy) 알고리즘인 다익스트라(Di
|
|
|
}
void main()
{
int i,set;
shortest_path(0,MAX_VERTICES); //0을 출발지로하는최단경로찾음
printf(\"0 = 출발점 \\n\\n\");
printf(\"Min distance 이동 경로 \\n\");
for (i=0; i< MAX_VERTICES; i++) { //최단경로값 ,도착위치출력
printf(\"%d %d\", distance[i], i);
set=i;
while (index[set] !=
|
|
메뉴펼치기
