응애맘마조

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다. 다익스트라 다이내믹 프로그래밍을 활용하여 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 흔히 인공위성이나 GPS 소프트웨어에서 흔하게 많이 사용됩니다. 최단 경로를 알려줄 때 음의 간선을 포함할 수 없기 때문에 현실세계에서 사용하기 매우 적합한 알고리즘입니다. 이 과정에서는 도착까지의 정점뿐만이 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 찾게 됩니다. 그래프 방향의 유무는 상관없지만, 만약 간선들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없고 ..