Рубрики

Java-программа для алгоритма Дейкстры с печатью путей

import java.util.Scanner; // Функция сканера, принимающая входные значения

  

public class Dijkstra

{

    static Scanner scan; // сканирование - это объект сканера

  

    public static void main(String[] args)

    {

        int[] preD = new int[5];

        int min = 999, nextNode = 0; // min содержит минимальное значение, nextNode содержит значение для следующего узла.

        scan = new Scanner(System.in);

        int[] distance = new int[5]; // матрица расстояний

        int[][] matrix = new int[5][5]; // фактическая матрица

        int[] visited = new int[5]; // посещенный массив

  

        System.out.println("Enter the cost matrix");

  

        for (int i = 0; i < distance.length; i++)

        {

            visited[i] = 0; // инициализируем посещенный массив нулями

            preD[i] = 0;

  

            for (int j = 0; j < distance.length; j++)

            {

                matrix[i][j] = scan.nextInt(); // заполнить матрицу

                if (matrix[i][j]==0)

                    matrix[i][j] = 999; // сделать нули 999

            }

        }

  

        distance = matrix[0]; // инициализируем массив расстояний

        visited[0] = 1; // установить исходный узел как посещенный

        distance[0] = 0; // устанавливаем расстояние от источника до источника до нуля, который является отправной точкой

  

        for (int counter = 0; counter < 5; counter++)

        {

            min = 999;

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

            {

                if (min > distance[i] && visited[i]!=1)

                {

                    min = distance[i];

                    nextNode = i;

                }

            }

  

            visited[nextNode] = 1;

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

            {

                if (visited[i]!=1)

                {

                    if (min+matrix[nextNode][i] < distance[i])

                    {

                        distance[i] = min+matrix[nextNode][i];

                        preD[i] = nextNode;

                    }

  

                }

  

            }

  

        }

  

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

            System.out.print("|" + distance[i]);

  

        System.out.println("|");

  

        int j;

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

        {

            if (i!=0)

            {

  

                System.out.print("Path = " + i);

                j = i;

                do

                {

                    j = preD[j];

                    System.out.print(" <- " + j);

                }

                while(j != 0);

            }

            System.out.println();

        }

    }

}

Эта программа предоставлена Раджем Миглани. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Java-программа для алгоритма Дейкстры с печатью путей

0.00 (0%) 0 votes