심플 이즈 베스트

글

라벨이 다익스트라 구현인 게시물 표시

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

4월 14, 2016

출발점, 도착점 사이의 최단 경로를 알아내는 알고리즘, 각 꼭지점은 도시를 나타내고 변은 도로의 길이를 나타날 때, 도시간 최단경로 찾기가 문제이다 최단 경로 찾기에선 가장 간단한 문제 이기도 할 것이다. 일단 5개의 도시로 고정되어있고, -1은 갈 수 없는 거리 0은 자기 자신을 표현한다. 알고리즘을 대략적으로 설계하면, for i -> 0 , 5 , 1 [시작도시][i]로 전체를 검사한다. 완전탐색이지만, 예외조건을 둔다 0과 -1을 제외하고, isVisit을 도시크기만큼 2차원 배열을 같이 두어 방문 체크를 한다. 그리고 최소값만을 Return하는 형식을 취하면 될 것 같다. 도시를 출력하고자 한다면, vector를 따로 두어, 경로를 push_back 하면 될 것 같긴하다. 테스트 케이스 및 자료는 [알고리즘 자료] 2-1 을 보시면 있습니다. #include #include using namespace std; int city[5][5] = { 0, }; bool isVisit[5][5] = { false, }; bool isFinal = false; bool isPossiblePath(int val) { if (val == 0 || val == -1) return false; return true; } void VisitCheck(int src, int dst) { isVisit[src][dst] = true; } void VisitUnCheck(int src, int dst) { isVisit[src][dst] = false; } int Dijkstra(int src,int dst,int fDst,int path) { path = path + city[src][dst]; if (dst == fDst) return path; // 하나의 경로를 찾은 것 int result = 9999; for (int i = 0; i 추...

이 블로그 검색

심플 이즈 베스트

글

진공 속 목소리: 의미 없는 세계에서 이유 찾기

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

이 블로그의 인기 게시물

윤석열 계엄령 선포! 방산주 대폭발? 관련주 투자 전략 완벽 분석

한국 핵무장 논의와 방위산업 관련주: 핵무기 개발 과정과 유망 종목 분석

[로스트아크] 제작 효율 최적화 위한 영지 세팅