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에 이르는 현재..
#include #include #include #define MAX 8 #define TRUE 1 #define FALSE 0 int cost[][MAX] = {{0,9999,9999,9999,9999,9999,9999,9999}, {300,0,9999,9999,9999,9999,9999,9999}, {1000,800,0,9999,9999,9999,9999,9999}, {9999,9999,1200,0,9999,9999,9999,9999}, {9999,9999,9999,1500,0,250,9999,9999}, {9999,9999,9999,1000,9999,0,900,1400}, {9999,9999,9999,9999,9999,9999,0,1000}, {1700,9999,9999,9999,9999,9999,..
#include #define n 8 #define m 5000 void main() { int data[8][8] = { {0,2,m,m,m,3,m,m}, {2,0,4,1,m,m,m,m}, {m,4,0,m,3,m,m,m}, {m,1,m,0,3,m,2,m}, {m,m,3,3,0,m,m,4}, {3,m,m,m,m,0,6,m}, {m,m,m,2,m,6,0,4}, {m,m,m,m,4,m,4,0}}; int i, j, k, s, e, min; int v[8], distance[8]; // 그래프는 사전에 주어진 그래프를 사용한다. 지금은 예를들어 표기를 한 것임. printf("\n \n"); printf("\n 주어진 그래프에서 출발점과 도착점을 입력하면 최단거리를 알려줍니다."); printf("\n +++..
Dijkstra 한 A지점에서 또다른 B지점 까지 가는 최단 거리를 구하는 알고리즘은 여러가지가 있습니다. 다익스트라(몇년전에 돌아가셨죠), 플로이드 등이 있습니다. 다익스트라 알고리즘은 A에서 B까지의 최단거리와 경로를 구하는 알고리즘 입니다. 플로이드 알고리즘은 모든 정점끼리의 최단거리를 구합니다. 다익스트라(Dijkstra, Edsger W. Dijkstra) 알고리즘은 A에서 B까지의 최단거리와 경로를 구합니다. 시간 복잡도는 O(N^2)-오더 N 제곱-입니다. 따라서 정점 100개가 있으면 10000번 이하의 반복으로 구할 수 있습니다. 원리는 그리디-욕심쟁이- 적으로 돌게 되지만 항상-거리가 음수(-) 이거나 싸이클이 없는 그래프 일 때- 최적해가 나옵니다. 그리고 다익스트라 알고리즘으로는 최..