Coding Test(최단 경로 - Dijkstra, Bellman-Ford, Floyd-Warsahall)

다익스트라 알고리즘(Dijkstra Algorithm)

특정한 노드에서 다른 모든 노드로의 최단경로를 구하는 알고리즘

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구함

그리디를 이용한 알고리즘으로 MST의 PRIM()과 유사

매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

<최단경로>

가중치 없는 경우	1		BFS
가중치 있는 경우	하나의 정점	양수	Dijkstra
		음수	Bellman-Ford
	모든 정점		Flod-Warsahall

 

1. 출발 노드를 설정한다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

5. 위 과정에서 3~4번을 반복한다.

 

INF로 초기화한 각 정점에 대해서 최소값을 저장해준다

list.add(new int[] {to, cost})로 그래프를 만들어주고 

 

start와 연결된 정점 중에서 dist[to]는 cost(start까지의 cost) + to_cost(to로 가기위한 cost) 가 된다.

 

 

import heapq #최소 힙
import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 최단거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번노드에서 b번 노드로 가는 비용c
  a,b,c = map(int, input().split())
  graph[a].append((b,c))

# 다익스트라 알고리즘(최소힙 이용))
def dijkstra(start):
  q=[]
  # 시작 노드
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

    # 이미 처리된 노드였다면 무시
    # 별도의 visited 테이블이 필요없이, 최단거리테이블을 이용해 방문여부 확인
    if distance[now] < dist:
      continue
    # 선택된 노드와 인접한 노드를 확인
    for i in graph[now]:
      cost = dist + i[1]
      # 선택된 노드를 거쳐서 이동하는 것이 더 빠른 경우
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  
# 다익스트라 알고리즘수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print("infinity")
  else:
    print(distance[i])

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_10282 {
	static List<int[]>[] data;
	static boolean[] visited;
	static int[] dist;

	/*
	 * 가중치 있는 방향 그래프 
     * 특정 노드에서 시작해서 다른 모든 노드까지의 경로를 모두 더함 => 다익스트라 알고리즘
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int t = Integer.parseInt(st.nextToken());
		for (int tc = 0; tc < t; tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			data = new ArrayList[n + 1];
			dist = new int[n + 1];
			visited = new boolean[n + 1];

			for (int i = 1; i < n + 1; i++) {
				dist[i] = Integer.MAX_VALUE;
				data[i] = new ArrayList<>();
			}

			for (int i = 0; i < d; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int s = Integer.parseInt(st.nextToken());

				data[b].add(new int[] { a, s });
			}

			dijkstra(c);

			int infection = 0;
			int total = 0;

			for (int i = 1; i < n + 1; i++) {
				if (dist[i] != Integer.MAX_VALUE) {
					infection++;
					total = Math.max(total, dist[i]);
				}
			}

			System.out.println(infection + " " + total);

		}

	}

	public static void dijkstra(int start) {
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
		dist[start] = 0;
		pq.add(new int[] { start, 0 });

		while (!pq.isEmpty()) {
			int[] temp = pq.poll();
			int to = temp[0];
			int cost = temp[1];

			if (!visited[to]) {
				visited[to] = true;
				for (int[] next : data[to]) {
					if (dist[next[0]] > cost + next[1]) { //cost == dist[to]
						dist[next[0]] = cost + next[1];
						pq.add(new int[] { next[0], dist[next[0]] });
					}
				}

			}
		}
	}

}

 

벨만 포드 알고리즘(Bellman-Ford)

플로이드 와샬 알고리즘(Flod-Warsahall)

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

다익스트라 알고리즘과 마찬가지로 단게별로 거쳐 가는 노드를 기준으로 알고리즘을 수행

=> 다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정 필요 x

다이나믹 프로그래밍 유형에 속한다