반응형
2. (A, D) -> (C, E) -> (D, F) -> (A, B) -> (B, E) -> (E, G)
3. A -> D -> F -> B -> E -> C -> G
4.
int selected[MAX_VERTICES];
int dist[MAX_VERTICES];
int get_min_vertex(int n)
{
int v, i;
for (i = 0; i <n; i++)
if (!selected[i]) {
v = i;
break;
}
for (i = 0; i < n; i++)
if (!selected[i] && (dist[i] < dist[v])) v = i;
return (v);
}
void prim(int s, int n)
{
int i, u, v;
for (u = 0; u<n; u++)
dist[u] = INF;
dist[s] = 0;
for (i = 0; i<n; i++)
{
u = get_min_vertex(n);
selected[u] = TRUE;
printf("selected ");
for (int i = 0; i < n; i++)
{
printf("%d ", selected[i]);
}
printf("\ndist ");
for(int i=0; i<n; i++){
printf("%d ", dist[i]);
}
printf("\n");
if (dist[u] == INF)
return;
printf("%d ", u);
for (v = 0; v<n; v++)
if (weight[u][v] != INF)
if (!selected[v] && weight[u][v]< dist[v])
dist[v] = weight[u][v];
}
}
//distance[]는 인접 정점의 가중치를 의미하고,
//selected[]는 선택한 정점을 의미한다.
6.
===============================
0 50 45 10 INF INF
INF 0 10 15 INF 6
INF INF 0 INF 30 INF
20 70 65 0 15 INF
INF 20 35 INF 0 INF
INF INF INF INF 3 INF
===============================
===============================
0 50 45 10 INF 56
INF 0 10 15 INF 6
INF INF 0 INF 30 INF
20 70 65 0 15 76
INF 20 30 35 0 26
INF INF INF INF 3 INF
===============================
===============================
0 50 45 10 75 56
INF 0 10 15 40 6
INF INF 0 INF 30 INF
20 70 65 0 15 76
INF 20 30 35 0 26
INF INF INF INF 3 INF
===============================
===============================
0 50 45 10 25 56
35 0 10 15 30 6
INF INF 0 INF 30 INF
20 70 65 0 15 76
55 20 30 35 0 26
INF INF INF INF 3 INF
===============================
===============================
0 45 45 10 25 51
35 0 10 15 30 6
85 50 0 65 30 56
20 35 45 0 15 41
55 20 30 35 0 26
58 23 33 38 3 29
===============================
===============================
0 45 45 10 25 51
35 0 10 15 9 6
85 50 0 65 30 56
20 35 45 0 15 41
55 20 30 35 0 26
58 23 33 38 3 29
===============================
7.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphNode
{
int vertex;
struct GraphNode* link;
} GraphNode;
typedef struct GraphType
{
int n;
GraphNode* adj_list[MAX_VERTICES];
} GraphType;
int distance[MAX_VERTICES]; /* 시작정점으로부터의 최단경로 거리 */
int found[MAX_VERTICES]; /* 방문한 정점 표시 */
GraphType* g;
void insert_node(GraphType* g, int u, int v)
{
GraphNode* node;
node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
}
int choose(int distance[], int n, int found[])
{
int i, min, minpos;
min = INT_MAX;
minpos = -1;
for (i = 0; i < n; i++)
if (distance[i] < min && !found[i]) {
min = distance[i];
minpos = i;
}
return minpos;
}
// Dijkstra의 최단 경로 프로그램
void shortest_path(int start, int n)
{
int i, u, w;
for (i = 0; i < g->n; i++) /* 초기화 */
{
distance[i] = weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i < n - 2; i++)
{
u = choose(distance, n, found)
found[u] = TRUE;
for (w = 0; w < n; w++)
if (!found[w])
while (g->adj_list[u]->vertex != w)
{
g->adj_list[u] = g->adj_list[u]->link;
}
if (distance[u] + g->adj_list[u] < distance[w])
distance[w] = distance[u] + g->adj_list[u];
}
}
8.
void shortest_path(int start, int n)
{
int i, u, w;
for (i = 0; i<n; i++) /* 초기화 */
{
distance[i] = weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i<n - 2; i++) {
u = choose(distance, n, found);
found[u] = TRUE;
printf("%d-> ", u);
for (w = 0; w<n; w++)
if (!found[w])
if (distance[u] + weight[u][w]<distance[w])
distance[w] = distance[u] + weight[u][w];
}
}
9.
// Dijkstra의 최단 경로 프로그램
void shortest_path(GraphType* g, int start)
{
int i, j, u, w;
for (i = 0; i<g->n; i++) /* 초기화 */
{
distance[i] = g->weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i<g->n-1; i++)
{
print_status(g);
u = choose(distance, g->n, found);
found[u] = TRUE;
printf("distance : ");
for ( j = 0; j < g->n-1; i++)
printf("%d ", distance[j]);
for (w = 0; w<g->n; w++)
if (!found[w])
if (distance[u] + g->weight[u][w]<distance[w])
distance[w] = distance[u] + g->weight[u][w];
}
}
10. cs1 -> cs2 -> cs3 -> cs5 -> cs4 -> cs6 -> cs7 -> cs8
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 12장 핵심정리를 가져오도록 하겠습니다.
반응형