방향 그래프 최단 경로를 구하는 알고리즘으로 유명한 다익스트라 알고리즘 ACM ICPC 대회에서 가끔 요구한다. #include using namespace std; int main() { int i,j,k,s,e,min,n=8; int path[8],path_cnt=0; // unconnect const int U=static_cast(-1)/2; int data[8][8] = { {0,2,U,U,U,3,U,U}, {2,0,4,1,U,U,U,U}, {U,4,0,U,3,U,U,U}, {U,1,U,0,3,U,2,U}, {U,U,3,3,0,U,U,4}, {3,U,U,U,U,0,6,U}, {U,U,U,2,U,6,0,4}, {U,U,U,U,4,U,4,0}}; bool v[8]; int distance[8],vi..
최단경로 구하기 (Shortest Path) 어떤 그래프 G의 정점 A에서 다른 어떤 정점 B로의 최단경로는 A에서 B로가는 경로를 가운데 가장 작은 가중치 합을 가지는 경로를 말한다. 1. 최단경로를 구하는 방법최단 경로는 앞에서 살펴본 최소 비용 신장트리와 같이 그리디 알고리즘으로 구할 수 없다. 그리디 알고리즘을 사용하면 왜 구할 수 없는지를 생각해보자. 그리디 알고리즘은 현재 상태에서 가장 최적의 것을 선택해 나가는 방법이다. 그러나, 특정한 두 점사이를 연결하는 여러개의 경로들이 있을때, 가장 작은 가중치 합을 가지는 경로를 찾는 것은 이 경로들의 공통되는 끝점에서 가장 짧은 에지만을 선택해서는 찾을 수 없다. 즉, 최단경로는 자기 자신의 가중치는 높아도 전체적인 경로가중치를 줄여주는 간선이 있..
출처: http://en.wikipedia.org/wiki A-star algorithm은 초기노드에서 목표노드까지의 경로를 찾는 graph searching algorithm. Best-first search의 한 종류인데, 그러면 best-first search는 과연 무엇인가? Best-first search : 어떤 rule에 따라서 가장 promising하다고 판단된 노드부터 먼저 방문하는 depth-first search를 최적화하는 graph search 알고리즘이다. 이때 어떤 rule이란, 노드에 대한 extra 정보를 의미함으로써, heuristic function을 정의한다. Dijkstra의 shortest path finding 알고리즘도 best-first search의 종류에 ..
Code: #include #include #include using namespace std; #define M 10000 #define countOfVtx 5 int dist[countOfVtx]; void Dijkstra(int (*G)[countOfVtx], int s) { list V1, V2; // vertex = set(V1) + set(V2) int path[countOfVtx]; //s에서 countOfVtx까지의 최단거리 int i, j, min, minJ; for(i=0;i
주어진 알고리즘을 c로 구현한 것입니다. 어디까지나 구현에 목적을 두었으므로 최적화된 코드가 아님을 알려드립니다.. // 최단경로 Dijkstra Algorithm을 이용한 해법 #include #include #define n 6 // 정점이 몇개인지를 정의 #define m 9999 // 연결되지 않은 정점끼리는 9999라는 값으로 끊어졌음을 표시.. int flag[n+1],dist[n+1]; // 거리 결정난곳 체크 배열과 거리 배열 int i,j,min,bk; // i,j는 for문 돌릴때 쓰는거 min은 최소값 갱신시 사용,bk는 위치 백업 int data[n+1][n+1] = { {0,0,0,0,0,0,0}, {0,0,2,m,3,m,m}, {0,m,0,4,1,m,m}, {0,m,m,0,4,1..
#include #include #include enum Boolean{FALSE, TRUE}; #define nmax 100 #define MAX 100000 int adjacant[10][10]={ {0, 1500, 250, MAX, MAX, MAX, MAX, MAX, MAX, MAX}, {1500, 0, 1000, 1200, 1400, MAX, MAX, MAX, MAX, MAX}, {250, 1000, 0, MAX, MAX, MAX, MAX, 1400, MAX, 900}, {MAX, 1200, MAX, 0, MAX, MAX, 800, 500, 1000, MAX}, {MAX, 1400, MAX, MAX, 0, 1200, MAX, MAX, MAX, MAX}, {MAX, MAX, MAX, MAX, 120..
*** 하나의 정점에서 다른 모든 정점까지의 최단 경로 *** 최단경로(ShortestpPath)는 v(시작정점)에서부터 t(목표점)까지의 경로로서 이 경로를 구성하는 아크(간선)들의 가중치 합이 최소가 되는 경로를 말한다. 가중치는 비용, 길이, 시간, 거리 등과 같은 뜻이다. 하나의 아크로 된 경로의 가중치 합보다 두개나 혹은 세개의 아크로 된 경로의 가중치 합이 작을수도 있다. 이러한 모든 경로를 길이의 순서로 나타내는것이 최단경로 알고리즘이라고 할수 있다. 먼저 S를 최단 경로가 이미 찾아져서 확정된 정점의 집합이라 하자. 처음에는 이 S에 시작점 v만 포함시킨다. 이 S에 포함되지 못한 정점 i에 대해 Dist[i]는 시작점 v에서부터 S에 포함되어 있는 정점만을 경유하여 정점 i에 이르는 현재..
