Cet article présente l'algorithme Dijkstra basé sur Java sous forme d'exemples. Je pense qu'il sera utile aux lecteurs pour étudier et apprendre les algorithmes du domaine de la structure des données.
Dijkstra a proposé un algorithme pour générer le chemin le plus court vers chaque sommet par ordre croissant de la longueur du chemin entre chaque sommet et le point source v. Autrement dit, trouvez d'abord le chemin le plus court avec la longueur la plus courte, puis utilisez-le pour trouver le chemin le plus court avec la longueur la plus courte suivante, et ainsi de suite, jusqu'à ce que tous les chemins les plus courts du point source v aux autres sommets soient trouvés.
L'implémentation du code est la suivante :
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //Cette route est bloquée public static void main(String[] args) { int[][] poids1 = {//Matrice de contiguïté {0, 3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] poids2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} } ; int start=0 ; dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("La distance la plus courte entre "+start+" et "+i+" est : "+shortPath[i ] ); } public static int[] dijkstra(int[][] poids, int start) { // Accepte une matrice de poids d'un graphe orienté et un numéro de point de départ start (numéroté à partir de 0, le sommet est stocké dans le tableau) // Renvoie un tableau int[], indiquant la longueur du chemin le plus court du début à celui-ci int n = poids.longueur ; //Nombre de sommets int[] shortPath = new int[n]; //Enregistre le chemin le plus court du début aux autres points String[] path = new String[n]; chemin du début vers d'autres points Représentation sous forme de chaîne pour (int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] approved = new int[n] //Marque si le chemin le plus court vers le sommet actuel has been Find, 1 signifie qu'il a été trouvé //Initialisation, le premier sommet a été trouvé shortPath[start] = 0; visited[start] = 1; for(int count = 1; count < n; count++) { //Pour ajouter n-1 sommets int k = -1; //Sélectionnez un sommet non marqué le plus proche du sommet initial start int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && poids[start][i] < dmin) { dmin = poids[start][i]; //Marque le sommet nouvellement sélectionné comme le chemin le plus court a été trouvé, et le chemin le plus court pour commencer est dmin shortPath[k] = dmin; visited[k] = 1; //Avec k comme point médian, corrige le chemin à partir de début à Distance des points non visités for(int i = 0; i < n; i++) { if(visited[i] == 0 && poids[start][k] + poids[k][i] < poids[début] [je]) { poids[début][i] = poids[début][k] + poids[k][i]; chemin[i] = chemin[k] + "-->" + i; 0; i < n; i++) { System.out.println("Le chemin le plus court de "+start+" à "+i+" est : "+path[i] } System.out.println("======================================"); }}Le résultat de l'exécution de ce programme est :
Le chemin le plus court de 0 à 0 est : 0-->0 Le chemin le plus court de 0 à 1 est : 0-->1 Le chemin le plus court de 0 à 2 est : 0-->3-->2 de Le chemin le plus court de 0 à 3 est : 0-->3 Le chemin le plus court de 0 à 4 est : 0-->3-->2-->4==== =================================La distance la plus courte de 0 à 0 est : 0 de 0 à 1 La distance la plus courte de 0 à 2 est : 50 La distance la plus courte de 0 à 3 est : 30 La distance la plus courte de 0 à 4 est : 60