Форум программистов, компьютерный форум, киберфорум
Java
Войти
Регистрация
Восстановить пароль
 
3 / 2 / 1
Регистрация: 04.04.2019
Сообщений: 158
1

Функции и переменные данного кода, алгоритм Дийкстры

24.11.2020, 22:20. Просмотров 2088. Ответов 0
Метки нет (Все метки)

Здравствуйте! Помогите разобратьсч дл чего нужны некоторые переменные
и как работают определенные функции. Думаю длч многих этот код, реализующий
алгоритм Дийкстры знаком.

Как работает функцич minDistance? Какие параметры передаютсч в неё, Что такое sptSet[] ?
Как пончть этот цикл внутри неё?

Сама функцич с алгоритмом, как пончть комментарий *The output array. dist[i] will hold * ?
Ну и этот кусок кода
Java
1
2
3
4
5
6
7
8
9
sptSet[u] = true; 
              // process adjacent nodes of the current vertex
            for (int v = 0; v < num_Vertices; v++) 
   
                // if vertex v not in sptset then update it  
                if (!sptSet[v] && graph[u][v] != 0 && path_array[u] != 
                            Integer.MAX_VALUE && path_array[u] 
                            + graph[u][v] < path_array[v]) 
                            path_array[v] = path_array[u] + graph[u][v];
Буду безумно благодарен, ибо сам не могу додуматьсч.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.*; 
import java.lang.*; 
import java.io.*; 
   
class Graph_Shortest_Path { 
     
    static final int num_Vertices = 6;  
  
    
    int minDistance(int path_array[], Boolean sptSet[])   { 
    
        int min = Integer.MAX_VALUE, min_index = -1; 
        for (int v = 0; v < num_Vertices; v++) 
            if (sptSet[v] == false && path_array[v] <= min) { 
                min = path_array[v]; 
                min_index = v; 
            } 
   
        return min_index; 
    } 
   
 
    void printMinpath(int path_array[])   { 
        System.out.println("Vertex# \t Minimum Distance from Source"); 
        for (int i = 0; i < num_Vertices; i++) 
            System.out.println(i + " \t\t\t " + path_array[i]); 
    }
    
 
    void algo_dijkstra(int graph[][], int src_node)  { 
        int path_array[] = new int[num_Vertices]; // The output array. dist[i] will hold 
        // the shortest distance from src to i 
   
 
            Boolean sptSet[] = new Boolean[num_Vertices]; 
   
        // Initially all the distances are INFINITE and stpSet[] is set to false 
        for (int i = 0; i < num_Vertices; i++) { 
            path_array[i] = Integer.MAX_VALUE; 
            sptSet[i] = false; 
        } 
   
        // Path between vertex and itself is always 0 
        path_array[src_node] = 0; 
   // now find shortest path for all vertices  
        for (int count = 0; count < num_Vertices - 1; count++) { 
            // call minDistance method to find the vertex with min distance
            int u = minDistance(path_array, sptSet); 
              // the current vertex u is processed
            sptSet[u] = true; 
              // process adjacent nodes of the current vertex
            for (int v = 0; v < num_Vertices; v++) 
   
                // if vertex v not in sptset then update it  
                if (!sptSet[v] && graph[u][v] != 0 && path_array[u] != 
                            Integer.MAX_VALUE && path_array[u] 
                            + graph[u][v] < path_array[v]) 
                            path_array[v] = path_array[u] + graph[u][v]; 
        } 
   
        // print the path array 
        printMinpath(path_array); 
    } 
}
class A111{
    public static void main(String[] args) 
    { 
        //example graph is given below
        int graph[][] = new int[][] { { 0, 2, 1, 0, 0, 0}, 
                                      { 2, 0, 7, 0, 8, 4}, 
                                      { 1, 7, 0, 7, 0, 3}, 
                                      { 0, 0, 7, 0, 8, 4}, 
                                      { 0, 8, 0, 8, 0, 5}, 
                                      { 0, 4, 3, 4, 5, 0} }; 
        Graph_Shortest_Path g = new Graph_Shortest_Path(); 
        g.algo_dijkstra(graph, 0); 
    } 
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.11.2020, 22:20
Ответы с готовыми решениями:

Алгоритм хеш функции SHA256. Разбор кода
Найден в интернете код алгортима SHA256, помогите разобраться в коде, что подается на вход, где...

Переменные,значение функции,вспомогательные переменные.
1)Даны переменные A,B,C.Изменить их значения,переместив их содержимое из A-в B,B-в C,C-в A,и...

Какие значения примут переменные с и d после исполнения данного алгоритма
Задан фрагмент алгоритма: Если a &lt; b, то c = b – a, иначе c =2*(a – b) d = 0 пока c &gt;a...

Недостатки данного кода С++
Здравствуйте, Уважаемые Форумчане! Подскажите, пожалуйста. Что не так в этом коде? Перечислите...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.11.2020, 22:20

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Алгоритм выполнения данного задания
Какое из приведенных имен удовлетворяет логическому условию ¬ (первая буква гласная -&gt; вторая буква...

Объясните смысл данного кода
Такой пример: int array; for_each(array, array + 5, (int &amp;p){p = 0;}); cout &lt;&lt; array; ...

Пояснить значение данного кода
int dRow = (row != 0 &amp;&amp; arr == (value - 1)) ? -1 : \ (row != (n - 1) &amp;&amp; arr == (value - 1)) ? 1...

Описать работу данного кода
Нашёл я код, который мне нужен, но не понимаю как тут что работает - в библиотеках algorithm,...

Проблемы/дедлоки данного кода
Всем привет, такой вопрос. Работаю с signalR в .net core , ее архитектура сильно похожа на webApi ,...

Прошу пояснить тонкости данного кода
#include &lt;math.h&gt; &lt;...&gt; class CAccumulator { private: float value; static int lastId; int...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.