[백준] 웜홀 - Python

시간이 되돌아가는 간선이 있기 때문에 간선 값 중에 음수가 존재합니다 따라서 음수 간선까지 계산할 수 있는 벨만포드 알고리즘을 사용하는 것이 불가피해 보입니다. 최단 거리 배열을 간선 갯수 + 1 길이에 0으로 초기화 합니다. 모든 최단 거리가 0이 되었기 때문에 일부 간선 값이 음수가 아닌 이상 최단거리 데이터는 갱신되지 않습니다. 여기서는 3번 -> 1번으로 가는 간선 값이 -3이기 때문...

벨만포드그래프코딩테스트그래프

Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 2

이전 Bellman Ford알고리즘에 이어서 포스팅합니다 :) 이번에도 이전 포스트와 마찬가지로 문제를 예시로 포스팅합니다. 노드는 총 5개(N), 그리고 이동할 수 있는 간선의 갯수는 총 8개(M)입니다. 이때 그래프를 그려보면 아래와 같이 그릴 수 있습니다. 위 그래프를 기반으로 다익스트라 알고리즘을 사용해서 문제를 해결해보도록 하겠습니다. 우선 다익스트라(Dijkstra)알고리즘은 우선...

다익스트라알고리즘벨만포드다익스트라

[Python] 백준 11657_타임머신+벨만포드 알고리즘 이론

벨만 포드 알고리즘 출발 노드 설정 최단 거리 테이블 초기화 다음의 과정을 N-1번 반복 -전체 간선 E개를 하나씩 확인 -각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 *만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한번 더 수행 -> 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재한다는 것. 다익스트라 알고리즘 vs 벨만 포드 알고리...

그래프이론코테공부백준벨만포드알고리즘그래프이론