# dijkstra

jeus

해당 문제를 풀면서 많은 어려움을 겪었다.. 오랜만에 다익스트라 알고리즘을 구현하는데 애먹었다. 다익스트라 알고리즘은 시작정점에서 이동가능한 정점까지 거리를 체크하고 체크한 값중 가장 작은 값인 정점에서 또 이동가능한 정점까지 거리를 체크해 나가는 방식이다. 구현할때

stn

그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단 비용을 구하는 알고리즘시작 노드의 비용을 0 으로 초기화 (본인에게 이동하는 비용은 0)우선 순위 큐에 시작 노드를 삽입 (연결 리스트로 구현하는 등 다른 방법도 있는 듯 하다)큐가 비어있을 때 까지 아래의 동

khyup0629

백준 13549번 숨바꼭질 3본 문제는 다익스트라 알고리즘을 이용하면 문제를 해결할 수 있습니다.그래프 문제에서 시작 노드에서 도착 노드가 이어져 있다는 것을 응용해서 해당 문제는 특정 칸에서 갈 수 있는 경우의 수를 3가지(+1, -1, X2)로 보면 됩니다.

khyup0629

백준 1753번 최단경로힙 자료구조를 이용해 다익스트라 알고리즘으로 문제를 해결할 수 있습니다.우선순위가 높은(거리가 가장 짧은) 노드를 힙에서 뽑아내 최단거리를 갱신합니다.

say_ye

가장 짧은 경로를 찾는 알고리즘을 의미한다.문제상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현특정한 출발

kimmy

문제는 (0,0)에서 시작해 (N-1, N-1)까지 갈 때 최소 비용을 구하는 것처음에는 dp를 풀 때 외발뛰기, 삼각형 위의 최대 경로 같은 문제들을 생각하며 dp로 풀어야 하나 생각했지만 링크는 동서남북으로 움직일 수 있으며 그때마다 이미 구했던 최적의 해는 바뀔

limelimejiwon

There are n cities connected by some number of flights. You are given an array flights where flights\[i] = $from_i$, $to_i$, $price_i$ indicates that

kldaji

Problem LinkFind all dijkstra results of vertexes.If the start node is same as "x", accumulate all distance results of vertexes.Otherwise, accumulate

yoopark

그래프 간선 방향을 역으로 바꾸면 생기는 일

xx0hn

이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 처음에는 백트레킹을 통해 경우의 수를 따져 구하려고 하였지만 다익스트라로 해결할 때에 훨씬 간단하게 해결할 수 있을 것이라는 생각을 중간에 하였고, 다익스트라로 거리를 체크하여 그 중 가장 큰 수를 걸리는 시간으로,

nuyh99

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시

seohyun-j

최단 경로 알고리즘이란,최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘최단 경로 문제의 종류하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제각 모든 정점에서 다른

yoopark

아주 전형적인 다익스트라 문제다. 하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.

kimmy

\[단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산우선 순위 큐에 지금까지 찾아낸 해당 정점까지의 최단 거리, 정점의 번호를쌍으로 넣음 priority_queue <pair<int, int>> pq; 정점까지의

boorook

분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)

boorook

분류: Shortest Path (최단거리), Binary Search (이분탐색)

xx0hn

이번 문제는 플로이드-와샬 알고리즘과 다익스트라 알고리즘을 사용하여 두번 풀어보았다. 우선 플로이드-와샬 알고리즘 풀이는 모든 정점에서 모든 정점으로의 최단 거리를 구하여 저장한 후에, 결과값들을 순회하며 최단 거리가 m 이하인 정점에 대한 아이템 수를 더하여 그 중

silver_star

https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로

silver_star

https://www.acmicpc.net/problem/2665단순히 시작 지점 \[0]\[0] -> 끝 지점 \[n-1]\[n-1]으로의 최단경로는 BFS로 해결 가능.하지만, 방을 바꾸는 최소 개수에 해당하는 경로는 최단경로가 아닐 수 있음시작 지점으로부

silver_star

https://www.acmicpc.net/problem/1504case 1) 1번 노드 -> v1 노드 -> v2 노드 -> n번 노드1번 노드 -> v1 노드 최단경로 다익스트라v1 노드 -> v2 노드 최단경로 다익스트라v2 노드 -> n번 노드 최단경로