728x90 반응형 벨만 포드1 [Algorithm] 다익스트라 (Dijkstra algorithm), 벨만 포드(Bellman ford algorithm) 그래프에서 특정 노드에서 특정 노드까지 가는 최단 거리를 구하는 알고리즘에 대해서 공부해보려 한다. 다익스트라 알고리즘과 벨만 포드 알고리즘이 있는데 이 둘의 차이는 그래프의 가중치가 음수를 허용하냐 허용하지 않냐의 차이다. 이 둘의 차이점을 기준으로 공부해보려 한다. Dijkstra algorithm 다익스트라 알고리즘은 음의 가중치를 허용하지 않고 양의 가중치만 존재할 때 최단 거리를 구하는 알고리즘이다. 최단 거리를 알고있는 노드와 최단 거리를 모르고있는 노드로 나눈다. 최단 거리를 모르고 있는 노드의 최단거리를 알아내는 것을 반복하는 알고리즘이다. A를 선택하고 연결된 노드 B와 C를 비교한다. 먼저 가장 짧은 거리인 5만큼 떨어져있는 C의 최단 경로는 5라고 확정할 수 있다. 여기서 의문이 생길.. 2022. 12. 19. 이전 1 다음 728x90 반응형
