노트정리/알고리즘
최단경로 - 다익스트라 , 플로이드 알고리즘
최단 경로는 어떤 정점 A에서 정점 Z까지의 최단 경로란 A에서 Z까지의 경로 중 간선의 가중치의 합이 가장 작은 경로 입니다. 단일 출발점 최단 경로- 단일 시작점에서 최단 경로 구하기 문제는 임의의 시작점을 1개 정하고 다른 노드들 사이의 최단 경로를 구하는데 사용.- 노드 사이의 거리가 모두 양수인 경우, 가장 널리 사용하는 것 다익스트라 알고리즘 다익스트라 알고리즘- 한 출발점에서 다른 모든 정점으로 최단 경로를 구하는 문제로 가중치를 갖는 간선은 없음. 모든 쌍 최단 경로- 모든 정점쌍 간의 최단 경로를 구하는 방법, 경로의 길이가 음인 사이클이 그래프에 존재하지 않을 것을 가정, 단일 출발점으로하여서 반복적으로 적용해 구할 수 있음.O(|V|s)- 경로의 길이가 음인 사이클이 그래프에 존재 X..