230302 공부내용 정리

임준성·2023년 3월 2일
0

알고리즘

목록 보기
8/8

230302 공부내용 정리


용어 정리

최단 경로 알고리즘

  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
  • 하나의 시작 정점에서 끝 정점까지의 최단 경로

    • 다익스트라(dijkstra)알고리즘

      • 음의 가중치를 허용하지 않음
      • 정점 중심 해결
    • 벨만-포드(Bellman_Ford)알고리즘

      • 음의 가중치 허용
      • 간선 중심 해결
  • 모든 정점들에 대한 최단 경로

    • 플로이드-워샬(Floyd-Warshall)알고리즘



Dijkstra 알고리즘

  • 시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

  • 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.

  • 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.



다익스트라 실습

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTest {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());

		int[][] adjMatrix = new int[V][V];

		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < V; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		final int INF = Integer.MAX_VALUE;
		int[] distance = new int[V]; // 출발정점에서 자신까지 오는 최소 비용
		boolean[] visited = new boolean[V]; // 경유지로 고려된 정점 여부

		Arrays.fill(distance, INF); // 최소값이 갱신 로직을 반영해야하므로 큰값으로 초기화
		distance[start] = 0;

		int min, current;
		for (int c = 0; c < V; c++) {

			// step1: 경유지로 처리되지 않은 정점 중 출발지에서 가장 가까운 정점 선택
			current = -1;
			min = INF;
			for (int i = 0; i < V; i++) {
				if (!visited[i] && min > distance[i]) {
					min = distance[i];
					current = i;
				}
			}

			if (current == -1)
				break; // 더이상 갈수있는 정점이 없다면
			visited[current] = true;
			
			// 선택된 정점이 문제에서 요구하는 도착정점이면 끝내기
			if(current==end)break;

			// step2: 위에서 선택된 정점을 경유지로 해서 갈 수 있는 다른 미방문 인접정점과의 비용 최고값 갱신
			for (int j = 0; j < V; j++) {
				if (!visited[j] && adjMatrix[current][j] != 0 && distance[j] > min + adjMatrix[current][j]) {
					distance[j] = min + adjMatrix[current][j];
				}
			}
		}
		System.out.println(distance[end]!=INF? distance[end] : -1);
	}
}
profile
아무띵크 있이

0개의 댓글