목록최단경로 (1)

코딩뚠뚠

[기본문제풀이] dijkstra algorithm

풀이 일시 : 2020-08-13 ​ 다익스트라 알고리즘 : 최단경로를 탐색하는 알고리즘이다. GPS등에 사용됨 음의간선이 존재하지 않는다. 최단거리는 여러개의 최단거리로 이루어져있다. 탐색하면서 최소비용인 것으로 갱신해나간다. ​ 문제 : 주어진 weight table을 보고 start 에서부터 최소비용을 추출하라 ​ 풀이1 : 선형탐색방법으로 구현 O(N^2) #include int number = 6; int INF = 10000000; int a[6][6] = { //weight table {0,2,5,1,INF,INF}, {2,0,3,2,INF,INF}, {5,3,0,3,1,5}, {1,2,3,0,1,INF}, {INF,INF,1,1,0,2}, {INF,INF,5,INF,2,0} }; bool ..
알고리즘 문제풀이/기본문제풀이 2020. 12. 28. 00:39
이전 Prev 1 Next 다음