알고리즘
최단경로 알고리즘
두구둥둥
2021. 4. 4. 22:10
최단경로 알고리즘이란 그래프에서 노드간의 최단경로를 찾는 알고리즘이다.
대표적인 최단경로 알고리즘
- BFS
- 다익스트라
- 벨만포드
- 플로이드 와샬
다음 표는 상황에 따라 어떤 알고리즘을 선택해야 하는지에 대한 표이다.
| 단일 노드 - 단일 노드 | 모든 노드 쌍 | ||
| Edge에 weight 없음 | BFS | 플로이드 와샬 알고리즘 | |
| Edge에 weight 있음 | 음수 weight 있음 | 벨만 포드 알고리즘 | |
| 음수 weight 없음 | 다익스트라 알고리즘 | ||
(출처. https://shnoh.tistory.com/15)
다익스트라 알고리즘
한 정점 A에서 다른 정점으로 가는 촤단경로를 구할 때 사용.
가중치는 0 또는 양수만 가능하다.
그리디를 이용한 알고리즘
O(V^2)
O((V+E)logV) // 우선순위 큐를 사용했을때
private void dijkstra(int V, int E, ArrayList<ArrayList<Node>> graph){
int[] distance = new int[V+1];
boolean[] visited = new boolean[V+1];
for (int i = 0; i < distance.length; i++) {
distance[i] = Integer.MAX_VALUE;
}
distance[1] = 0;
visited[1] = true;
for (Node node : graph.get(1)) {
distance[node.e] = node.weight;
}
int minIdx,min;
int sum=0;
for (int i = 1; i < V-1; i++) {
minIdx = 0;
min = Integer.MAX_VALUE;
//방문 안한 노드 중 distance값이 가장 작은거 찾기
for (int j = 0; j < distance.length; j++) {
if(visited[j]) continue;
if(min>distance[j]){
min = distance[j];
minIdx = j;
}
}
visited[minIdx] = true;
//찾은 노드의 인접으로 distance 갱신
for (Node node : graph.get(minIdx)) {
if(visited[node.e]) continue;
distance[node.e] = Math.min(distance[minIdx]+node.weight,distance[node.e]);
}
}
System.out.println(Arrays.toString(distance));
}벨만포드 알고리즘
한 정점 A에서 다른 정점으로 가는 최단경로를 구할 때 사용
가중치는 음수, 0, 양수 모두 가능
DP를 이용한 알고리즘
음의 사이클이 생기면 음의 무한이 되기 때문에 사이클이 발생하는지 체크 필수!
O(V^3) = O(VE) //평균적으로 간선의 개수는 노드의 제곱으로 본다.
private void bellman(int V, int E, int[][] edges){
int[] distance = new int[V+1];
boolean[] visited = new boolean[V+1];
boolean isUpdated;
for (int i = 1; i <= V; i++) {
distance[i] = INF;
}
distance[1] = 0;
for (int i = 1; i <= V; i++) { // 경로 길이 V-1, V가 되면 사이클 생긴거
isUpdated = false;
for (int[] edge : edges) {
if(distance[edge[1]]>distance[edge[0]]+edge[2]){
distance[edge[1]]=distance[edge[0]]+edge[2];
isUpdated = true;
if(i==V){
System.out.println("음의 사이클 발생!!!");
return;
}
}
}
if(!isUpdated) break; //아무런 변화 없으므로 조기 종료!
}
System.out.println(Arrays.toString(distance));
}플로이드 와샬 알고리즘
모든 정점간의 최단경로를 구할 때 사용
가중치는 음수, 0, 양수 모두 가능
DP를 이용한 알고리즘
음의 사이클 체크 필수
O(V^3)
private void floid(int V, int E, ArrayList<ArrayList<Node>> graph){
int[][] distance = new int[V+1][V+1];
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
distance[i][j] = INF;
}
}
for (int i = 1; i <=V; i++) {
for (Node node : graph.get(i)) {
distance[i][node.e] = node.weight;
}
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 1; k <= V; k++) {
if(distance[j][i]!=INF && distance[i][k]!=INF)
distance[j][k] = Integer.min(distance[j][k],distance[j][i]+distance[i][k]);
}
}
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
System.out.print(distance[i][j]+" ");
}
System.out.println();
}
}전체 코드
package shortest_path;
import java.util.ArrayList;
import java.util.Arrays;
public class Shortest_path {
private final int INF = Integer.MAX_VALUE;
static class Node{
int e,weight;
public Node(){
}
public Node(int e, int weight){
this.e = e;
this.weight = weight;
}
}
public static void main(String[] args) {
int V = 4, E = 7;
//int V = 8,E=11;
int[][] edges = {{1,2,4},{1,3,1},{2,3,2},{2,4,1},{3,2,1},{4,1,5},{4,3,5}};
//int[][] edges = {{1,2,3},{1,5,4},{1,4,4},{2,3,2},{3,4,1},{4,5,2},{5,6,4},{4,7,6},{7,6,3},{3,8,3},{6,8,2}};
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(new Node(edge[1],edge[2]));
}
System.out.println("1에서 출발하는 다익스트라");
new Shortest_path().dijkstra(V,E,graph);
System.out.println("플로이드와샬");
new Shortest_path().floid(V,E,graph);
System.out.println("1에서 출발하는 벨만포드");
new Shortest_path().bellman(V,E,edges);
}
private void bellman(int V, int E, int[][] edges){
int[] distance = new int[V+1];
boolean[] visited = new boolean[V+1];
boolean isUpdated;
for (int i = 1; i <= V; i++) {
distance[i] = INF;
}
distance[1] = 0;
for (int i = 1; i <= V; i++) { // 경로 길이 V-1, V가 되면 사이클 생긴거
isUpdated = false;
for (int[] edge : edges) {
if(distance[edge[1]]>distance[edge[0]]+edge[2]){
distance[edge[1]]=distance[edge[0]]+edge[2];
isUpdated = true;
if(i==V){
System.out.println("음의 사이클 발생!!!");
return;
}
}
}
if(!isUpdated) break; //아무런 변화 없으므로 조기 종료!
}
System.out.println(Arrays.toString(distance));
}
private void floid(int V, int E, ArrayList<ArrayList<Node>> graph){
int[][] distance = new int[V+1][V+1];
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
distance[i][j] = INF;
}
}
for (int i = 1; i <=V; i++) {
for (Node node : graph.get(i)) {
distance[i][node.e] = node.weight;
}
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 1; k <= V; k++) {
if(distance[j][i]!=INF && distance[i][k]!=INF)
distance[j][k] = Integer.min(distance[j][k],distance[j][i]+distance[i][k]);
}
}
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
System.out.print(distance[i][j]+" ");
}
System.out.println();
}
}
private void dijkstra(int V, int E, ArrayList<ArrayList<Node>> graph){
int[] distance = new int[V+1];
boolean[] visited = new boolean[V+1];
for (int i = 0; i < distance.length; i++) {
distance[i] = Integer.MAX_VALUE;
}
distance[1] = 0;
visited[1] = true;
for (Node node : graph.get(1)) {
distance[node.e] = node.weight;
}
int minIdx,min;
int sum=0;
for (int i = 1; i < V-1; i++) {
minIdx = 0;
min = Integer.MAX_VALUE;
//방문 안한 노드 중 distance값이 가장 작은거 찾기
for (int j = 0; j < distance.length; j++) {
if(visited[j]) continue;
if(min>distance[j]){
min = distance[j];
minIdx = j;
}
}
visited[minIdx] = true;
//찾은 노드의 인접으로 distance 갱신
for (Node node : graph.get(minIdx)) {
if(visited[node.e]) continue;
distance[node.e] = Math.min(distance[minIdx]+node.weight,distance[node.e]);
}
}
System.out.println(Arrays.toString(distance));
}
}