벨만포드알고리즘1

• 

  벨만-포드(Belman-Ford) 알고리즘 & 다익스트라(Dijkstra) 알고리즘 & A* 알고리즘 이렇게 3개의 알고리즘을 하나로 묶은 이유는, 모두 최단 경로를 찾는 알고리즘이기 때문입니다. 최단 경로 문제- 시작점, 끝점이 정해져있음.- 가중 그래프가 주어졌을 때, 최단 경로를 구해야 합니다.  벨만-포드(Belman-Ford) 알고리즘- 음수 비용이 있을 경우에도 사용 가능합니다.- 첫 위치를 0로, 나머지 위치를 ∞로 설정해 놓는다. ex) A에서 G로 갈때, 최단 경로를 구하시오.1) A를 0으로,  나머지를 ∞로 설정합니다.2) 간선(A-B)을 골라 거리를 구합니다. (B : 9, A: 0)2) 또 다른 간선(A-C)을 구해 최단 거리를 구합니다. (C: 2)3) 또 다른 간선(B-C)를 구해 최단 거리를 구합니다. (B : 8)4) 또 다른 간선(B-E), (B-D)을 구해 최단 거리를 .. CS 지식/자료구조_알고리즘 2025. 1. 14.