NineTwo meet you

플로이드 와샬(Floyd Warshall) 모든 쌍의 최단 거리 알고리즘 두 정점 사이에 간선이 없는 경우 어떤 경로의 길이보다도 큰 값으로 처리 3중 for문 사용 자기 자신으로 가는 간선은 항상 0으로 초기화 int n; // 정점의 수 int m; // 간선의 수 int adj[][] = new int[n+1][n+1]; // 그래프의 인접행렬 // 간선이 없는 경우 어떤 경로의 길이보다 큰 값으로 초기화 // 자기 자신으로 가는 간선 0으로 초기화 for(int i = 0; i v 로 향하는 가중치 w를 가지는 간선 for(int i = 0; i < m; i++) { Str..

벨만 포드 (Bellman-Ford) 단일 시작점 최단 경로 알고리즘 음수 간선 포함 가능 동작 과정 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다. 최단 경로는 최대 V개의 정점을 갖기 때문에 잘해야 V-1개의 간선을 가질 수 있다. 따라서 모든 간선에 대한 완화 과정은 V-1번이면 충분하다. 음수 사이클 판정 완화를 V번 시도하면 된다. 음수 사이클이 존재하지 않다면 V-1번이면 최단 거리를 찾아낼 수 있다. 만일 V번째 완화 과정에서 한번더 완화가 성공한다면 이는 음수 사이클이 존재한다고 생각할 수 있게 된다. static int n; // 정점의 개수 static int m; // 간선의 개수 static ArrayList[] al = new ArrayList[n+1]; // 그래프의..

다익스트라(Dijsktra) 단일 시작점 최단거리 알고리즘 너비 우선 탐색(BFS)과 유사한 형태를 가진 알고리즘 큐 대신 우선순위 큐(PriorityQueue)를 사용해 최단 거리를 기준으로 정점을 배열해 문제를 해결 음수 간선을 포함할 수 없음 동작 과정 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화 출발 노드 기준 각 노드별 최소 비용 저장 방문하지 않은 노드 중 가장 최소 비용 노드 선택 해당 노드를 거쳐 특정 노드로 가는 경우 고려해 최소 비용 갱신 3,4 반복 1. 기본 그래프 확인 2. 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화한다. 출발 노드 0의 최소 비용을 0으로 초기화한다. 3. 출발 노드 기준 각 노드별 최소 비용 저장한다. 출발 노드 0을 기준으로 연결된 노드..