DijkstraSSSP (řešení pro nejkratší cestu s jedním zdrojem) (implementace Java) (matice sousedství) (prioritní fronta) (minimální hromada)

Dijkstrasssp



Implementační kód

/* 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 } }

Algoritmické nápady

  • Na začátku je zdrojový bod přidán k nejkratší posloupnosti cest a vzdálenost k dalším vrcholům je nastavena na nekonečno
  • Vyberte vrchol vi s nejmenší vzdáleností od zdrojového bodu od nevybraných vrcholů a přidejte nejkratší posloupnost cest
  • Aktualizujte nejkratší vzdálenost od zdrojového bodu přes vrchol vi ke všem ostatním vrcholům
  • Fronta priority se používá k výběru vrcholu nejblíže zdrojovému bodu a časová složitost je O (lg | V |)
  • Opakujte, dokud nejsou vybrány všechny vrcholy v nejkratší posloupnosti cest
  • Časová složitost algoritmu O (| V | ^ 2)

Testovací data

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

Výsledek výstupu

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

Ukázkové ilustrace

dík

poděkovat Královské fórum Cenné rady poskytované jejími produkty
Výše uvedený algoritmus Dijkstra je založen na Liu Rujia a Chen Feng Algoritmická klasifikace přihlášených do soutěže: průvodce tréninkem Dijkstrův algoritmus



Nakonec

  • Algoritmus Dijkstra se nevztahuje na případy záporných vedlejších vah a k řešení případu záporných vedlejších vah lze použít algoritmus Bellman-Ford.
  • Chcete-li vyřešit nejkratší cestu mezi všemi vrcholy, můžete použít Dijkstrův algoritmus s každým vrcholem jako zdrojovým bodem, s časovou složitostí O (| V | ^ 3), nebo použít Floydův algoritmus s časovou složitostí O (| V | ^ 3), ale existence záporných okrajových vah může být povolena a smyčka složená z hran se zápornými hranovými vahami není povolena.
  • Vzhledem k omezené úrovni bloggerů jsou nevyhnutelná opomenutí. Čtenáři mohou kdykoli kritizovat a opravit, aby nedocházelo ke zbytečným nedorozuměním!