[알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘(Dijkstra's Algorithm)

그래프에서 특정 정점에서 다른 모든 정점까지의 최단거리를 찾는 알고리즘. DP를 이용함
이 알고리즘은 음의 가중치를 가지지 않는 그래프에서 사용됨

주로 GPS 경로 탐색, 네트워크 라우팅, 지도app에서 최단 경로를 계산할때 활용됨

DP인 이유
최단거리는 여러 개의 최단거리로 이루어져있기 때문!

다익스트라는 현재까지 알고 있던 최단 경로를 계속해서 갱신힘
왜냐면. 1->3으로 간다고 가정해보자

1- (7) -> 3
1- (2) -> 2 - (1) ->3

컴퓨터는 당장 하나씩 밖에 계산하지 못하기 때문에 1에 직접적으로 붙어있는 노드까지의 최단거리를 먼저 구함
따라서 7로 먼저 구했다가 3으로 갱신하게됨

동작 과정
1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장함. 출발 노드 기준으로 바로 방문하지 못하는 노드는 무한으로 놔둠
3. 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택함
4. 해당 노드를 거쳐서 특정한 노드를 가는 경우를 고려하여 최소 비용 갱신. 기존 값에 더하는 방식(이것이 DP)
5. 3,4번을 반복

다익스트라 알고리즘은 이렇게 동적 프로그래밍(DP)을 사용했기 때문에 소스코드가 짧고 간결함

A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요?

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 다익스트라 알고리즘이 효율적일까요?

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?

🫠

출처: https://m.blog.naver.com/ndb796/221234424646