벨만-포드(Bellman-Ford) 알고리즘
1. 그래프에서 최단 경로를 찾는 알고리즘 중 하나
2. 간선비용이 양수,음수에서 모두 정상 동작함.
: 간선 비용은 시간,거리,요금을 나타내서 양수가 일반적임.
: 그러나 간선 비용이 음수인 경우에도 정상 동작함 (다익스크라는 음수인 간선에선 동작하지X)
3. 음수 사이클
: 음수 사이클이 있는 경우 거리를 무한히 줄이게되서, 최단 경로를 정의할 수 없음. (최단거리가 존재X)
구현 코드

function bellmanFord(graph, start, end) {
const numOfNodes = graph.length; // 10
const distance = Array(numOfNodes).fill(Infinity); // [0, 8, 2, 4, 9, 10, 13]
const predecessor = Array(numOfNodes).fill(null); // [null, 2, 0, 2, 1, 3, 5];
distance[start] = 0;
// V-1번 반복하며 최단 거리 갱신 (0~8)
for (let i = 0; i < numOfNodes - 1; i++) {
for (let [u, v, w] of graph) {
if (distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
predecessor[v] = u;
}
}
}
// 음수 사이클 확인
for (let [u, v, w] of graph) {
if (distance[u] + w < distance[v]) {
console.log('음수 사이클이 존재합니다.');
return null;
}
}
// 최단 경로 출력
const path = []; // [0,2,3,5,6] [A,C,D,F,G]
let currentNode = end;
while (currentNode !== null) {
path.unshift(currentNode);
currentNode = predecessor[currentNode];
}
return { distance: distance[end], path: path };
}
// 그래프 예시: [출발노드, 도착노드, 가중치]
const graph = [
// u v w
[0, 1, 9], // A -> B 1 0
[0, 2, 2], // A -> C 2 0
[1, 4, 1], // B -> E 3 0
[1, 3, 3], // B -> D 4 0
[2, 3, 2], // C -> D 5 0
[2, 5, 9], // C -> F 6 0
[3, 4, 5], // D -> E 7 0
[3, 5, 6], // D -> F 8 0
[4, 6, 7], // E -> G 8 0
[5, 6, 4], // F -> G
];
// 노드를 숫자로 매핑: A=0, B=1, C=2, D=3, E=4, F=5, G=6
const startNode = 0; // A
const endNode = 6; // G
const result = bellmanFord(graph, startNode, endNode);
if (result) {
console.log('최단 거리:', result.distance);
console.log(
'최단 경로:',
result.path.map((n) => String.fromCharCode(65 + n)).join(' -> ')
);
}
벨만 포드 알고리즘
[백준]타임머신 - https://www.acmicpc.net/problem/11657
// SUCCESS
const file = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = file[0].split(' ').map(Number); // n : 도시의 개수(노드), m : 버스 노선의 개수(간선)
const info = file.slice(1, m + 1).map(line => line.split(' ').map(Number));
const INF = 1e9;
const distance = new Array(n + 1).fill(INF);
function bellmanFord(start) {
distance[start] = 0;
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
const [currentNode, nextNode, cost] = info[j];
if(distance[currentNode] !== INF && distance[nextNode] > distance[currentNode] + cost) {
distance[nextNode] = distance[currentNode] + cost;
if(i === n - 1) return true;
}
}
}
return false;
}
if(bellmanFord(1)) { // 음수 순환 확인되는 경우
console.log(-1);
} else { // 1번 노드 다음부터 출력
for(let i = 2; i <= n; i++) console.log(distance[i] === INF ? -1 : distance[i]);
}
'CS > 자료구조&알고리즘' 카테고리의 다른 글
이진 탐색 트리(Binary Search Tree) (0) | 2024.07.24 |
---|
벨만-포드(Bellman-Ford) 알고리즘
1. 그래프에서 최단 경로를 찾는 알고리즘 중 하나
2. 간선비용이 양수,음수에서 모두 정상 동작함.
: 간선 비용은 시간,거리,요금을 나타내서 양수가 일반적임.
: 그러나 간선 비용이 음수인 경우에도 정상 동작함 (다익스크라는 음수인 간선에선 동작하지X)
3. 음수 사이클
: 음수 사이클이 있는 경우 거리를 무한히 줄이게되서, 최단 경로를 정의할 수 없음. (최단거리가 존재X)
구현 코드

function bellmanFord(graph, start, end) {
const numOfNodes = graph.length; // 10
const distance = Array(numOfNodes).fill(Infinity); // [0, 8, 2, 4, 9, 10, 13]
const predecessor = Array(numOfNodes).fill(null); // [null, 2, 0, 2, 1, 3, 5];
distance[start] = 0;
// V-1번 반복하며 최단 거리 갱신 (0~8)
for (let i = 0; i < numOfNodes - 1; i++) {
for (let [u, v, w] of graph) {
if (distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
predecessor[v] = u;
}
}
}
// 음수 사이클 확인
for (let [u, v, w] of graph) {
if (distance[u] + w < distance[v]) {
console.log('음수 사이클이 존재합니다.');
return null;
}
}
// 최단 경로 출력
const path = []; // [0,2,3,5,6] [A,C,D,F,G]
let currentNode = end;
while (currentNode !== null) {
path.unshift(currentNode);
currentNode = predecessor[currentNode];
}
return { distance: distance[end], path: path };
}
// 그래프 예시: [출발노드, 도착노드, 가중치]
const graph = [
// u v w
[0, 1, 9], // A -> B 1 0
[0, 2, 2], // A -> C 2 0
[1, 4, 1], // B -> E 3 0
[1, 3, 3], // B -> D 4 0
[2, 3, 2], // C -> D 5 0
[2, 5, 9], // C -> F 6 0
[3, 4, 5], // D -> E 7 0
[3, 5, 6], // D -> F 8 0
[4, 6, 7], // E -> G 8 0
[5, 6, 4], // F -> G
];
// 노드를 숫자로 매핑: A=0, B=1, C=2, D=3, E=4, F=5, G=6
const startNode = 0; // A
const endNode = 6; // G
const result = bellmanFord(graph, startNode, endNode);
if (result) {
console.log('최단 거리:', result.distance);
console.log(
'최단 경로:',
result.path.map((n) => String.fromCharCode(65 + n)).join(' -> ')
);
}
벨만 포드 알고리즘
[백준]타임머신 - https://www.acmicpc.net/problem/11657
// SUCCESS
const file = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = file[0].split(' ').map(Number); // n : 도시의 개수(노드), m : 버스 노선의 개수(간선)
const info = file.slice(1, m + 1).map(line => line.split(' ').map(Number));
const INF = 1e9;
const distance = new Array(n + 1).fill(INF);
function bellmanFord(start) {
distance[start] = 0;
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
const [currentNode, nextNode, cost] = info[j];
if(distance[currentNode] !== INF && distance[nextNode] > distance[currentNode] + cost) {
distance[nextNode] = distance[currentNode] + cost;
if(i === n - 1) return true;
}
}
}
return false;
}
if(bellmanFord(1)) { // 음수 순환 확인되는 경우
console.log(-1);
} else { // 1번 노드 다음부터 출력
for(let i = 2; i <= n; i++) console.log(distance[i] === INF ? -1 : distance[i]);
}
'CS > 자료구조&알고리즘' 카테고리의 다른 글
이진 탐색 트리(Binary Search Tree) (0) | 2024.07.24 |
---|