[アルゴリズム]Dijkstraアルゴリズム

マルチアウトレットアルゴリズム

1つの始点から別のすべての頂点までの最短距離を計算するアルゴリズム.
BFSと同様の形状を有し,BFSとは異なり重み付けされた図形にも適用できる.
△短音の幹線を含めるべきではない.
また,最短距離を求める際には,以前に求めた最短距離情報を用いたため,動的プログラミングの問題といえる.

floodとshallアルゴリズム:すべてのペアの最短距離計算

ベルマンフォードアルゴリズム:マルチ出力に似ていますが、負の重み付けのグラフィックにも適用されます.

オペレーションプロセス

1.現在のノードを基準として、各ノードに格納される最小コスト.
-配列の使用(インデックス:ノード/値:コスト)
2.未処理ノードの中で最もコストの低いノードを選択します.
-優先キューを使用すると、O(logn)の時間的複雑さが得られます.
3.2では、選択したノードのパスを考慮して、各ノードの最小コストを更新する.
-ノードの最小コストが更新された場合は、ノードを通過するパスを再検討し、優先キューに入れる必要があります.
-すべての幹線を検査する必要があるので、O(E)の時間的複雑さがある.
4.上記の手順を繰り返します.
−O(E＊logN)の時間的複雑さを有する.

例

上記図面では、1番ノードを先頭ノードとして、マルチ出力アルゴリズムの適用を試みる
まず、1番ノードに格納されるすべての隣接ノードの最小コスト.
これによりdist配列は上記と同様になり、優先キューには更新コストが最も低い2番ノードと3番ノードが含まれます.

次に、優先キューで最もコストの低いノードを選択します.ここでは3番ノードを選択します.
3番ノード付近の幹線を確認します.1番ノードの料金dist[1]は0になっているのでスキップします.
1ノードから4ノードまでの最低コストは

dist[4]:現在格納1ノードから4ノードまでの最低コスト

.

dist[3]+w(3,4):1番ノードから3番ノードまでの最小コスト+e(1,3)重み付け.つまり、3日から4日までの

この2つの値のうち、より小さい値です.
現在dist[4]はINFであるため、dist[4]=dist[3]+w(3,4)=2+6=8となる.

次に2番ノードを選択します.
2番ノードが隣接するノードのうち、4番ノードのコストは現在格納されているコストより2番ノード低いため、4番ノードのコストを更新することができる.
dist[4] = dist[2] + w(2,4) = 4 + 1 = 5
(キューには既にコスト8の4番ノード情報が含まれているが、4番ノードまでの最小コストが更新されているため、無意味なデータとみなすことができるので省略した.)

4番ノードを選択します.
更新するデータがないため終了し、dist配列は1番ノードから他のすべてのノードまでの最短距離を格納する

インプリメンテーション

[白俊]1753号:最短経路
この問題によりコードが実現された.

import java.util.*;

class Pair implements Comparable<Pair>{
    int vertex;
    int weight;
    public Pair(int vertex,int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
    @Override
    public int compareTo(Pair pair) {
        return this.weight > pair.weight ? 1 : - 1;
    }

}
public class Solution {
    static int INF = 100000000;
    public static void main(String args[]) {
        // 입력
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        int k = sc.nextInt();

        List<Pair>[] graph = new ArrayList[V+1];
        for(int i=1; i<=V; i++)
            graph[i] = new ArrayList<>();

        // 그래프 생성
        for(int i=0; i<E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph[u].add(new Pair(v,w));
        }
        // dist 배열 무한대 값으로 초기화
        int[] dist = new int[20001];
        Arrays.fill(dist, INF);

        // 시작 점의 거리 0으로 설정하고 우선순위큐에 삽입
        dist[k] = 0;
        PriorityQueue<Pair> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(new Pair(k,0));

        while(!priorityQueue.isEmpty()) {
            // 최소거리가 가장 작은 노드 선택
            Pair curv = priorityQueue.poll();
            List<Pair> adjacentList = graph[curv.vertex];

            //만약 현재 노드까지의 거리가 이미 저장된 시작~현재노드의 거리보다 크면 비교할 필요X
            //현재 노드를 지나가서는 최단거리가 될 수 없음
            if (curv.weight > dist[curv.vertex])
                continue;

            // 현재 노드에 인접한 노드들 확인
            for(Pair nextv : adjacentList) {
                // 현재 노드를 거쳐가는 비용이 더 적으면 갱신 후 우선순위 큐에 삽입
                if(dist[nextv.vertex] > dist[curv.vertex] + nextv.weight) {
                    dist[nextv.vertex] = dist[curv.vertex] + nextv.weight;
                    priorityQueue.add(new Pair(nextv.vertex, dist[nextv.vertex]));
                }
            }
        }
        for(int i=1;i<=V;i++) {
            String res = dist[i] == INF ? "INF" : Integer.toString(dist[i]);
            System.out.println(res);
        }
    }
}

            // 현재 노드에 인접한 노드들 확인
            for(Pair nextv : adjacentList) {
                // 현재 노드를 거쳐가는 비용이 더 적으면 갱신 후 우선순위 큐에 삽입
                if(dist[nextv.vertex] > dist[curv.vertex] + nextv.weight) {
                    dist[nextv.vertex] = dist[curv.vertex] + nextv.weight;
                    priorityQueue.add(new Pair(nextv.vertex, dist[nextv.vertex]));
                }
            }
        }
        for(int i=1;i<=V;i++) {
            String res = dist[i] == INF ? "INF" : Integer.toString(dist[i]);
            System.out.println(res);
        }
    }
}

✨ Comparable, Comparator

両方のインタフェースは、オブジェクトの比較を作成するために使用されます.
差異

Compability:langパッケージにあり、インポートする必要はありません.
compareTo(T o)メソッドには1つのパラメータしかありません.
-自身をパラメータオブジェクトと比較します.

Comparator:utilパッケージに存在します.
compare(To 1,To 2)メソッドには2つのパラメータがある.
-パラメータとして入力した2つのオブジェクトを比較します.