벨만포드1

• 

  210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부 벨만-포드(Bellman-Ford) 벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 ) 초기화 : 간선 검사 순서 임의로 정하는 등등 앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌 정점의 개수 - 1 번 만큼 반복 시간복잡도 : ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 ) 다익스트라(Dijkstra) Greedy 알고리즘이라고 할 수 있음 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘 효율적, 실생활에서 많이 사용됨 ex) gp.. 미가공 필기(알고리즘) 2021. 7. 13.