목록Dijkstra (1)

Patrick's Devlog

[Algorithm] Dijkstra Algorithm(다익스트라 알고리즘)

1. Dijkstra Algorithm 음의 가중치가 없는 그래프의 한 정점(Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 처음 알고리즘의 시간복잡조는 O(V^2)이나, 우선순위 큐 등을 이용해 더욱 개선된 알고리즘이 나오면서 최종적으로 O((V+E)logV)의 시간복잡도를 가지게 되었다. 여기서 V는 정점의 개수, E는 한 정점의 주변 노드이다. 그래프 방향 유무는 상관없으나, 간선(Edge)중 하나라도 가중치가 음수이면 알고리즘은 사용될 수 없다. 다익스트라를 확장시킨 알고리즘이 바로 A* 알고리즘이다. 1-1. Aigorithm P[A][B] -> A와 B사이의 거리라고 가정 1. 출발점으로부터 최단거리를 저장할 배열 d[v] 생성, 출발 노드에는 0을 출발점을 제외한 다른..
Study/Algorithms & Data Structure 2022. 11. 8. 16:21
이전 Prev 1 Next 다음