심플 이즈 베스트

글

라벨이 최단 경로 알고리즘인 게시물 표시

[알고리즘] 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++] 다익스트라를 활용한 최단 경로찾기

4월 14, 2016

구성되는 test.txt파일은 test.txt 0 3 0 5 8 -1 -1 -1 0 1 4 2 -1 -1 0 3 2 4 4 -1 0 1 -1 -1 2 1 0 로 구성되며 그림으로 나타내면, 첫째 줄 0은 출발도시, 3은 도착 도시이고, -1은 갈 수 없는 경로, 0 은 자기자신을 의미한다. 이를 토대로 결과 값은 출력 예로는 위 그림과 같이 출력된다. 소스코드는 [알고리즘] 2-1을 보시면 구현 되어있습니다. 추가로 읽으면 좋을 것

이 블로그 검색

심플 이즈 베스트

글

우연과 필연의 교차로에서: 삶의 이유를 해부하다

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

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

이 블로그의 인기 게시물

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

대통령 퇴진운동 관련주: 방송·통신·촛불수혜주 완벽 분석

키움 OPEN API MFC 개발 (1)