Рубрики

Java-программа для алгоритма кратчайшего пути Дейкстры | Жадный Алго-7

По заданному графу и исходной вершине в графе найдите кратчайшие пути от источника ко всем вершинам данного графа.

Алгоритм Дейкстры очень похож на алгоритм Прима для минимального остовного дерева . Как и MST Prim, мы генерируем SPT (дерево кратчайшего пути) с заданным источником в качестве root. Мы поддерживаем два набора, один набор содержит вершины, включенные в дерево кратчайшего пути, другой набор включает вершины, еще не включенные в дерево кратчайшего пути. На каждом шаге алгоритма мы находим вершину, которая находится в другом наборе (набор еще не включен) и имеет минимальное расстояние от источника.

Ниже приведены подробные шаги, используемые в алгоритме Дейкстры для нахождения кратчайшего пути от одной исходной вершины ко всем остальным вершинам данного графа.
Алгоритм
1) Создайте набор sptSet (набор дерева кратчайших путей), который отслеживает вершины, включенные в дерево кратчайших путей, т. Е. Минимальное расстояние от источника которого рассчитывается и завершается. Изначально этот набор пуст.
2) Назначьте значение расстояния для всех вершин входного графа. Инициализируйте все значения расстояния как БЕСКОНЕЧНЫЙ. Назначьте значение расстояния как 0 для исходной вершины, чтобы она выбиралась первой.
3) Хотя sptSet не включает в себя все вершины
…. a) Выберите вершину u, которой нет в sptSet и которая имеет минимальное значение расстояния.
…. б) Включите u в sptSet .
…. c) Обновить значение расстояния всех смежных вершин u. Чтобы обновить значения расстояния, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v сумма значений расстояния u (от источника) и веса ребра uv меньше значения расстояния v, то обновите значение расстояния v.

Джава

// Java-программа для алгоритма кратчайшего пути Дейкстры с одним источником.
// Программа для представления графа в матрице смежности

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ShortestPath {

    // Полезная функция для поиска вершины с минимальным значением расстояния,

    // из множества вершин, еще не включенных в дерево кратчайших путей

    static final int V = 9;

    int minDistance(int dist[], Boolean sptSet[])

    {

        // Инициализируем минимальное значение

        int min = Integer.MAX_VALUE, min_index = -1;

  

        for (int v = 0; v < V; v++)

            if (sptSet[v] == false && dist[v] <= min) {

                min = dist[v];

                min_index = v;

            }

  

        return min_index;

    }

  

    // Утилита для печати построенного массива расстояний

    void printSolution(int dist[], int n)

    {

        System.out.println("Vertex   Distance from Source");

        for (int i = 0; i < V; i++)

            System.out.println(i + " tt " + dist[i]);

    }

  

    // Функция, которая реализует кратчайший путь Дейкстры с одним источником

    // алгоритм для графа, представленного с использованием матрицы смежности

    // представление

    void dijkstra(int graph[][], int src)

    {

        int dist[] = new int[V]; // Выходной массив. dist [i] будет держать

        // кратчайшее расстояние от источника до меня

  

        // sptSet [i] будет истинным, если вершина i включена в кратчайший

        // дерево пути или кратчайшее расстояние от src до i завершено

        Boolean sptSet[] = new Boolean[V];

  

        // Инициализируем все расстояния как INFINITE, а stpSet [] как false

        for (int i = 0; i < V; i++) {

            dist[i] = Integer.MAX_VALUE;

            sptSet[i] = false;

        }

  

        // Расстояние исходной вершины от себя всегда равно 0

        dist[src] = 0;

  

        // Находим кратчайший путь для всех вершин

        for (int count = 0; count < V - 1; count++) {

            // Выбираем минимальное расстояние вершины из множества вершин

            // еще не обработано. ты всегда равен src в первом

            // итерация.

            int u = minDistance(dist, sptSet);

  

            // Пометить выбранную вершину как обработанную

            sptSet[u] = true;

  

            // Обновляем значение dist соседних вершин

            // выбранная вершина.

            for (int v = 0; v < V; v++)

  

                // Обновляем dist [v], только если нет в sptSet, есть

                // ребро от u до v и общий вес пути от src до

                // v через u меньше текущего значения dist [v]

                if (!sptSet[v] && graph[u][v] != 0 && 

                   dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])

                    dist[v] = dist[u] + graph[u][v];

        }

  

        // выводим построенный массив расстояний

        printSolution(dist, V);

    }

  

    // Метод драйвера

    public static void main(String[] args)

    {

        / * Давайте создадим примерный граф, обсужденный выше * /

        int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

                                      { 4, 0, 8, 0, 0, 0, 0, 11, 0 },

                                      { 0, 8, 0, 7, 0, 4, 0, 0, 2 },

                                      { 0, 0, 7, 0, 9, 14, 0, 0, 0 },

                                      { 0, 0, 0, 9, 0, 10, 0, 0, 0 },

                                      { 0, 0, 4, 14, 10, 0, 2, 0, 0 },

                                      { 0, 0, 0, 0, 0, 2, 0, 1, 6 },

                                      { 8, 11, 0, 0, 0, 0, 1, 0, 7 },

                                      { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

        ShortestPath t = new ShortestPath();

        t.dijkstra(graph, 0);

    }

}
// Этот код предоставлен Aakash Hasija

Выход:

Vertex   Distance from Source
0 tt 0
1 tt 4
2 tt 12
3 tt 19
4 tt 21
5 tt 11
6 tt 9
7 tt 8
8 tt 14

Пожалуйста, обратитесь к полной статье об алгоритме кратчайшего пути Дейкстры | Жадный Алго-7 для более подробной информации!

Рекомендуемые посты:

Java-программа для алгоритма кратчайшего пути Дейкстры | Жадный Алго-7

0.00 (0%) 0 votes