최단경로문제
페이지 정보
작성일 22-10-13 02:10본문
Download : 최단경로문제.hwp
Download : 최단경로문제.hwp( 19 )
최단경로문제에 대한 글입니다.
레포트/기타
최단경로문제
순서
최단경로알고리즘
,기타,레포트
1. 동적계획법 (Floyd 알고리즘)
2. Greedy 설계법 (Dijkstra 알고리즘)
3. 두 알고리즘 비교/평가
=>설명(說明)
②번의 최단거리의 1행( 0 1 3 1 4 5)와 ④번의 각 정점에 대한 (최단거리: x)를 비교해보면 같음을 알수 있따(호로그램이 제대로 구현되었음을 의미)
Dijkstra 알고리즘에서 테스트1의 그래프(grape.dat)를 동일한 것으로 했다.최단경로알고리즘 , 최단경로문제기타레포트 ,
다.
▶테스트2 (파일명: floyd2.dat)
▶실행결과2
=>설명(說明)
②번의 최단거리의 1행( 0 2 6 3 6 3 5 9 )와 ④번의 각 정점에 대한 (최단거리: x)를 비교해보면 같은을 알수 있따(호로그램이 제대로 구현되었음을 의미)
2. Greedy - Dijkstra 알고리즘
▶dijkstra 알고리즘 소스(파일명: dijkstra.cpp)
#include
#include
#include //파일에 입출력을 위해서
using std::ofstream;
using std::ifstream;
//이음선 구조체 定義(정의)
struct edge {
int start_v;
int end_v;
};
const int MAX=1…(省略)
설명
최단경로문제에 대한 글입니다. ④번의 결과를 유심히 봐두면 좋겠다. Floyd 알고리즘과 결과를 비교하기 위해서이다.