# Bellman Ford
[Algorithm] 다익스트라 vs 벨만포드 vs 플로이드와샬
그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단 비용을 구하는 알고리즘시작 노드의 비용을 0 으로 초기화 (본인에게 이동하는 비용은 0)우선 순위 큐에 시작 노드를 삽입 (연결 리스트로 구현하는 등 다른 방법도 있는 듯 하다)큐가 비어있을 때 까지 아래의 동
[Algorithm] Shortest Path - 최단경로 알고리즘
최단 경로 알고리즘이란,최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘최단 경로 문제의 종류하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제각 모든 정점에서 다른
[알고리즘][파이썬] 벨만-포드 알고리즘
그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기
벨만포드(Bellman-Ford) 알고리즘이란 무엇인가?
벨만포드 알고리즘이란? 다익스트라 알고리즘과 마찬가지로 최단경로를 구하는 알고리즘입니다. 다익스트라는 음의 간선이 없을 경우에만 사용이 가능하지만, 벨만포드 알고리즘의 경우 음의 간선이 있을 때에도 최단거리를 구할 수 있습니다. 하지만 다익스트라 알고리즘보다 느립니다.
백준 1219번: 오민식의 고민
백준 1219번: 오민식의 고민기본 아이디어는 골목길 문제와 비슷하다.간선을 탈 때 빼주고, 노드에 도착했을 때 더해준다. 이 문제도 도착점까지 가는 경로에 사이클이 있는 경우에만 Gee를 출력해야 한다. 골목길 문제는 1부터 N까지 순서대로 V-1번 루프를 돌고 마지
백준 1738번: 골목길
백준 1738번: 골목길음의 간선을 포함한 최단거리 찾기. 이 때 단순히 사이클이 존재한다고 -1을 출력하는 것이 아니라, 1부터 N까지 가는 길에 사이클이 존재하여 N에 도착했을 때 금품을 무한히 가질 수 있는 경우에만 -1을 출력해야 한다. 예를 들어, N=5이고,
백준 11657번: 타임머신
백준 11657번: 타임머신음의 간선이 존재하기 때문에 다익스트라 알고리즘으로는 최단거리를 찾을 수 없다. 따라서 O(VE)로 모든 경우의 수를 탐색하는 벨만 포드 알고리즘이 적합. i가 1씩 커질때마다 싸이클을 한번씩 돈다고 하면, 500바퀴 돌렸을 때 INT_MIN
[C] 백준 11657 타임머신
https://www.acmicpc.net/problem/11657 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동...
[백준] 11657번-(Python 파이썬) - Bellman-Ford
문제링크 : https://www.acmicpc.net/problem/11657이번 문제는 가중치가 음수인 경우가 있어 다익스트라가 아니라 벨만포드 알고리즘으로 풀어야한다.벨만포드 알고리즘은 다익스트라에 비해 느리므로 가중치가 음수인경우에만 사용하는게 좋다.기
[백준]#1738 골목길
문제민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는
[백준]#1219 오민식의 고민
문제오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.오민식은 고민에 빠졌다.어떻게 하면 최대 이윤을 낼 수 있을까?이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의
[백준]#11657 타임머신
문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인
[백준]#1865 웜홀
문제때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을
[알고리즘] Bellman-Ford in python3
Dijkstra 다음은 Bellman-Ford 알고리즘이죠. MIT 6006 강좌의 17번째 강의입니다. 개인적으로는 Dijkstra보다 원리가 훨씬 단순해서 더 이해하기 편했습니다. 구현의 경우에도 negative cycle을 체크하는 코드 정도가 추가되었을 뿐 Dijkstra의 경우보다 짧아졌습니다.