알고리즘 문제풀이/기본문제풀이
[기본문제풀이] floydwarshall
로디네로
2020. 12. 28. 00:42
반응형
풀이 일시 : 2020-08-13
플로이드와샬 알고리즘 :
그래프 정점간 최단거리를 구하는 알고리즘 중 모든 최단 경로를 구하는 방법이다. (다익스트라는 한 점에서 다른점까지의 최단 경로) 또한 플로이드와샬에서는 음의 가중치를 가진 간선을 사용할 수 있다.
모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다.
문제 :
주어진 인접행렬에서 플로이드 와샬 알고리즘을 사용하여 모든 거리를 구하라
{0 , 5 , inf , 8},
{7 , 0 , 9 , inf},
{2 , inf , 0 , 4},
{inf , inf , 3 , 0}
풀이 :
#include <stdio.h>
int number = 4;
int inf = 10000000;
int a[4][4] = {
{0,5,inf,8},
{7,0,9,inf},
{2,inf,0,4},
{inf,inf,3,0}
};
void floydWarshall() {
int d[4][4];
//그래프를 초기화한다.
for (int i = 0; i < number; i++) {
for (int j = 0; j < number; j++) {
d[i][j] = a[i][j];
}
}
for (int k = 0; k < number; k++) { //0 1 2 3
for (int i = 0; i < number; i++) {
for (int j = 0; j < number; j++) {
if (d[i][k] + d[k][j] < d[i][j]) { //k를 거쳐가는경우를 따져준다.
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
//출력
for (int i = 0; i < number; i++) {
for (int j = 0; j < number; j++) {
printf("%3d ", d[i][j]);
}
printf("\n");
}
}
int main() {
floydWarshall();
}
반응형