은비블로그

음의 가중치가 없는 그래프의한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 [시간복잡도]O((V+E)logV)이지만열결 그래프라면 O(ElogV)까지 줄일 수 있다.일반적으로는 우선순위 큐를 이용하는 것이 낫다고 한다. [매커니즘]1 ) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택2 ) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 [초기화]A노드에서 A노드로 가는 가는 지점이 가장 짧다.라고 정의 [알고리즘 적용]방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하며 값 갱

음수 사이클이 없는 그래프 내의모든 정점에서 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘. *음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아왔을 때 최종 비용이 음수인 사이클 다이나믹 프로그래밍 기법을 사용한 알고리즘.인접 행렬을 이용해서 각 노드간 최소 비용을 계산한다.한 정점에서 한 정점까지 가는 경로의 간선 개수를 0개에서 N개까지 모두 고려. 0개의 간선을 거쳐 가는 경우는 자기 자신밖에 없기 때문에초기 그래프의 모양은 (r, c) (r==c)을 제외하고 모드 매우 큰 값으로 초기화해준다.연결되지 않는 경로는 매우 큰 값으로 초기화되어 있을 것이다. 코드 // 플로이드 초기 거리 테이블 초기화 dist = new int[N][N]; for (int i = 0; i  ..