В этой статье представлен алгоритм Дейкстры, основанный на Java, в виде примеров. Я считаю, что она будет полезна читателям при изучении и изучении алгоритмов предметной области структуры данных.
Дейкстра предложил алгоритм генерации кратчайшего пути к каждой вершине в порядке возрастания длины пути между каждой вершиной и исходной точкой v. То есть сначала найдите кратчайший путь с наименьшей длиной, а затем используйте его для поиска кратчайшего пути со следующей наименьшей длиной и так далее, пока не будут найдены все кратчайшие пути от исходной точки v до других вершин.
Реализация кода следующая:
package com.algorithm.impl; public class Dijkstra { Private static int M = 10000; //Эта дорога заблокирована public static void main(String[] args) { int[][] Weight1 = {//Матрица смежности {0, 3 ,2000,7,М}, {3,0,4,2,М}, {М,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] вес2 = { {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; int[] shortPath =; dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("Кратчайшее расстояние от "+start+" до "+i+": "+shortPath[i ] ); } public static int[] dijkstra(int[][] вес, int start) { //Принимает матрицу весов ориентированного графа и номер начальной точки start (нумерация начинается с 0, вершина сохраняется в массиве) //Возвращает массив int[], указывающий длину кратчайшего пути от начала до нее int n = Weight.length ; //Количество вершин int[] shortPath = new int[n] //Сохраняем кратчайший путь от начала до других точек String[] path = new String[n]; путь от начала до других точек Строковое представление for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visit = new int[n] //Отмечаем, есть ли кратчайший путь к текущей вершине был Find, 1 означает, что она найдена //Инициализация, первая вершина найдена shortPath[start] = 0; visit[start] = 1; for(int count = 1; count < n; count++) { //Чтобы добавить n-1 вершин int k = -1; //Выберите непомеченную вершину, ближайшую к начальной вершине start int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && вес[start][i] < dmin) { dmin = вес[start][i] k = i } }; //Отметьте вновь выбранную вершину как найденный кратчайший путь, а кратчайший путь для начала — dmin shortPath[k] = dmin; visit[k] = 1 //Исправив путь от k в качестве средней точки; start to Расстояние от непосещенных точек for(int i = 0; i < n; i++) { if(visited[i] == 0 && Weight[start][k] + Weight[k][i] < Weight[start] [я]) { вес[start][i] = вес[start][k] + вес[k][i]; путь[i] = путь[k] + "-->" + i; } } } for(int i = 0; i < n; i++) { System.out.println("Кратчайший путь от "+start+" до "+i+": "+path[i]); System.out.println("==================================="); return shortPath; }}Результатом запуска этой программы является:
Кратчайший путь от 0 до 0: 0-->0 Кратчайший путь от 0 до 1: 0-->1 Кратчайший путь от 0 до 2: 0-->3-->2 из Самый короткий путь от 0 до 3: 0-->3 Кратчайший путь от 0 до 4: 0-->3-->2-->4==== ================================Кратчайшее расстояние от 0 до 0: 0 от 0 до 1 Кратчайшее расстояние от 0 до 2: 50 Кратчайшее расстояние от 0 до 3: 30 Кратчайшее расстояние от 0 до 4: 60