データ構造とアルゴリズム

DijkstraSSSP（単一ソース最短パスソリューション）（Java実装）（隣接行列）（優先キュー）（最小ヒープ）



Dijkstrasssp



実装コード

/* author : eclipse email : root@xxxxx time : Thu Apr 16 16:45:05 2020 */ import java.util.PriorityQueue import java.util.Comparator import java.util.Vector import java.util.Scanner public class Map { private static int INF = 0x7fff private int vexNum private int[][] matrix//Adjacency matrix private int[] dijkstraSSSP//Maintain the shortest path private void createNet(Vector<Edge> v) { //The adjacency matrix establishes an undirected network matrix = new int[vexNum][vexNum] for (int i = 0 i < vexNum i++) { for (int j = 0 j < vexNum j++) { matrix[i][j] = INF } } for (int i = 0 i < v.size() i++) { matrix[v.elementAt(i).start][v.elementAt(i).destination] = v.elementAt(i).dis matrix[v.elementAt(i).destination][v.elementAt(i).start] = v.elementAt(i).dis } } public Map(Vector<Edge> v, int num) { vexNum = num createNet(v) } public void dijkstra(int start) { PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>(1, new Comparator<Vertex>() { public int compare(Vertex v1, Vertex v2) { return v1.dis - v2.dis } })//Priority queue, minimum heap, the smaller the edge weight, the higher the priority dijkstraSSSP = new int[vexNum] boolean[] tag = new boolean[vexNum]//Vertex access mark int[] dist = new int[vexNum]//The shortest distance from the source point start to each vertex for(int i = 0 i < vexNum i++) { tag[i] = false dist[i] = INF//Initially infinity } pq.add(new Vertex(start, 0)) dist[start] = 0 dijkstraSSSP[start] = start + 1 Vertex v = null while (!pq.isEmpty()) { v = pq.poll() int top = v.num if (tag[top]) { //If the vertex has been visited, continue to search for other vertices continue } tag[top] = true//Mark the vertex has been visited for (int i = 0 i < vexNum i++) { //Update the path from the source point start to vertex i through vertex top, and the path distance from vertex top to i is shorter //It can be obtained immediately after vexNum updates, the shortest path and distance from the source point start to all other vertices if(dist[i] > dist[top] + matrix[top][i]){ //Core code part //If there are two paths from the source point start to top and top to i //And the sum of the distances of the two paths is less than the distance from the source point start to i (other paths) //Update the shortest distance dist[i] = dist[top] + matrix[top][i] dijkstraSSSP[i] = top + 1 pq.add(new Vertex(i, dist[i]))//Add the vertex of the updated distance to the priority queue } } } System.out.println('Dijkstra Shortest Distance') for (int i = 0 i < vexNum i++) { System.out.printf('%d ', dijkstraSSSP[i]) } System.out.println(' Dijkstra Shortest Path') for (int i = 0 i < vexNum i++) { System.out.printf('%d ', dist[i]) } } public static void main(String[] args) { Scanner sc = new Scanner(System.in) Vector<Edge> v = new Vector<Edge>() int N = sc.nextInt() int source = sc.nextInt() int max = -1 for (int i = 0 i < N i++) { int start = sc.nextInt() int destination = sc.nextInt() int dis = sc.nextInt() v.add(new Edge(start - 1, destination - 1, dis)) max = Integer.max(max, start) max = Integer.max(max, destination) } Map map = new Map(v, max) map.dijkstra(source - 1) } } class Vertex { int num int dis public Vertex(int n, int d) { this.num = n this.dis = d } } class Edge { int start int destination int dis public Edge(int s,int des, int d) { this.start = s this.destination = des this.dis = d } }

アルゴリズムのアイデア

  • 最初に、ソースポイントが最短パスシーケンスに追加され、他の頂点までの距離が無限大に設定されます
  • 選択されていない頂点からソースポイントからの距離が最小の頂点viを選択し、最短パスシーケンスを追加します
  • ソースポイントから頂点viを経由して他のすべての頂点までの最短距離を更新します
  • 優先キューは、ソースポイントに最も近い頂点を選択するために使用され、時間計算量はO（lg | V |）です。
  • 最短経路シーケンスですべての頂点が選択されるまで繰り返します
  • アルゴリズムの時間計算量O（| V | ^ 2）

テストデータ

6 1 1 2 2 1 4 8 2 3 3 2 5 5 3 4 2 3 5 6

出力結果

Dijkstra Shortest Distance 1 1 2 3 2 Dijkstra Shortest Path 0 2 5 7 7

サンプルイラスト

ありがとう

感謝 キングリーフォーラム その製品によって提供される貴重なアドバイス
上記のダイクストラアルゴリズムは、LiuRujiaとChenFengのアルゴリズムに基づいています。 アルゴリズムコンペティションエントリークラシック：トレーニングガイド ダイクストラのアルゴリズム



やっと

  • ダイクストラアルゴリズムは負のサイドウェイトの場合には適用されず、ベルマンフォードアルゴリズムを使用して負のサイドウェイトの場合を解決できます。
  • すべての頂点間の最短経路を解くには、各頂点をソースポイントとしてO（| V | ^ 3）の時間計算量でダイクストラのアルゴリズムを使用するか、O（| V）の時間計算量でフロイドのアルゴリズムを使用します。 | ^ 3）、ただし、負のエッジの重みの存在は許可され、負のエッジの重みを持つエッジで構成されるループは許可されません。
  • ブロガーのレベルが限られているため、避けられない省略があります。読者は、不必要な誤解を避けるために、いつでも批判して訂正することを歓迎します！