후라이

오늘은 최단경로 문제에 빈출되는 알고리즘들에 대해 이론 설명을 해보겠습니다.알고리즘 공부를 처음 하시는 분들은 최단경로 문제를 풀이할 때, 다익스트라, 벨만 포드, 플로이드 워샬 등의알고리즘 기법이 헷갈리거나 익숙치 않을 수 있습니다. 기초를 단단히 다지고 넘어가는 게 좋을 것 같아요:) 우선, 최단 경로 탐색 알고리즘에는 종류가 많습니다. 각각의 특징과 목적에 따라 사용됩니다.(여기선 Dijkstra, Bellman-Ford, Floyd-Warchall만 알아봅시다)단일 출발지 최단 경로 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘ex) 다익스트라, 벨만-포드, A 알고리즘, SPFA(Shortest Path Faster Algorithm)모든 쌍 최단 경로 알고리즘그..

https://www.acmicpc.net/problem/1753 해당 백준 문제는 다익스트라 알고리즘을 사용한, 최단 경로를 구하는 문제이다.우선, 다익스트라 알고리즘에 대해 설명해보도록 하겠다. 1. 다익스트라 알고리즘이란?https://www.youtube.com/watch?v=pVfj6mxhdMw 첨부한 유튜브 영상을 통해 쉽게 이해할 수 있지만다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.이 알고리즘은 비음수 가중치를 가진 그래프에서만 사용할 수 있다. - 방향 그래프 또는 무방향 그래프- 각 간선에 대한 비음수 가중치- 시작 정점 위 세가지가 주어지면, 시작 정점에서 모든 정점까지의 최단 거리를 구하면 된다.여기서 간선 가중치..