목록알고리즘 (1)

시작이 반

벨만-포드 (Bellman-Ford)

벨만포드는 음수간선이 있을때 시작 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘이다. 시간복잡도 : O(VE) Edge( [u, v, cost] .... ) dist[처음 시작 노드] = 0 나머지 INF for( i 노드 개수 V ) for( j 간선 개수 E ) 출발 노드 = Edge[j][0] -> u 도착 노드 = Edge[j][1] -> v 비용 = Edge[E][2] -> cost if ( dist[출발노드] == 무한 ) continue; if ( dist[도착노드] > dist[출발노드] + cost ) dist[도착노드] = dist[출발노드] + cost ***********중요*********** if ( i == V - 1 ) 음수 사이클 존재
알고리즘/활용 방법 2021. 9. 15. 01:48
이전 Prev 1 Next 다음