반응형

플로이드 워셜 알고리즘의 코드 구현은 다음 사이트의 내용을 참조하였다.


http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/


그리고 플로이드 워셜 알고리즘이 진행되는 과정은 다음 게시물에 수록되어 있다.


http://www.crocus.co.kr/536 :: 플로이드 워셜 개념









<< 플로이드 워셜 알고리즘(Floyd Warshall Algorithm) 소스 코드 >> 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<stdio.h>
#include <limits.h>
 
// 정점의 수를 지정한다.
#define V 5
 
// INF를 무한대라고 지정하고, INT_MAX를 이용한다.
#define INF 10000
 
 
 
// 플로이드 워셜의 결과를 출력하는 함수
void printSolution(int dist[][V])
{
    printf("Following matrix shows the shortest distances, between every pair of vertices \n\n");
 
    printf("\t   to→ ");
 
    for (int i = 0; i < V; i++)
        printf("[%d]    ",i);
 
    printf("\n      ↓from \n");
 
    for (int i = 0; i < V; i++)
    {
        printf("\t[%d]", i);
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s""INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
 
// 모든 경로에 대한 최단 거리를 찾아주는 플로이드 워셜 함수
void floydWarshall(int graph[][V])
{
    /*
        dist[][] 배열에 최단 거리에 대한 정보들이 모두 들어가게 된다.
    */
    int dist[V][V], i, j, k;
 
    /*
        dist[][] 배열에 초기값은 그래프에서 주어진 값들이다.
        (즉, 아직 최단 거리를 구하기 전에는 기존의 거리를 최단 거리라 생각한다.)
    */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
 
    /*
        플로이드 워셜 알고리즘의 핵심
    */
    // 한 점을 경유하여
    for (k = 0; k < V; k++)
    {
        // x에서
        for (i = 0; i < V; i++)
        {
            // y로 갈때
            for (j = 0; j < V; j++)
            {
                // 최단거리면 업데이트 해준다.
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // 모든 최단거리가 구해지고 난 뒤, 출력을 해준다.
    printSolution(dist);
}
 
 
int main()
{
    int graph[V][V] = 
    {
        { 0845},
        { 7062},
        { 3203},
        { 7370},
        { 3742},
    };
 
    // 플로이드 워셜 알고리즘으로 진입
    floydWarshall(graph);
 
    return 0;
}
Crocus








결과 값은 다음과 같고, 이 과정에 대한 내용은 http://www.crocus.co.kr/536 에 자세히 수록되어 있다.


반응형