Dijkstra

    [백준] 1504 - 특정한 최단경로 (자바 Java)

    [Gold IV] 특정한 최단 경로 - 1504 문제 링크 성능 요약 메모리: 308324 KB, 시간: 1352 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오...

    [백준] 9370 - 미확인 도착지 (자바 Java)

    [Gold II] 미확인 도착지 - 9370 문제 링크 성능 요약 메모리: 283148 KB, 시간: 1220 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교..

    [알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

    목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..

출처: https://gmnam.tistory.com/157 [Voyager:티스토리]