Меню

Як реалізувати алгоритм Дейкстри в Java

how implement dijkstra s algorithm java

Спробуйте Наш Інструмент Для Усунення Проблем

Цей підручник пояснює, як реалізувати алгоритм Дейкстри на Java, щоб знайти найкоротші маршрути в графіку чи дереві за допомогою прикладів:

У нашому попередньому навчальному посібнику з графіків на Java ми побачили, що графіки використовуються для пошуку найкоротшого шляху між вузлами, крім інших програм.

Щоб знайти найкоротший шлях між двома вузлами графа, ми здебільшого використовуємо алгоритм, відомий як “ Алгоритм Дейкстри '. Цей алгоритм залишається широко використовуваним алгоритмом пошуку найкоротших шляхів у графіку або дереві.

=> Перевірте ВСІ підручники Java тут

Алгоритм Дейкстри на Java

Що ви дізнаєтесь:

Алгоритм Дейкстри на Java

Враховуючи зважений графік і вихідну (вихідну) вершину в графіку, алгоритм Дейкстри використовується для знаходження найкоротшої відстані від вихідного вузла до всіх інших вузлів на графіку.

В результаті запущеного алгоритму Дейкстри на графіку ми отримуємо дерево найкоротшого шляху (SPT) із вихідною вершиною як коренем.

В алгоритмі Дейкстри ми підтримуємо два набори або списки. Одна містить вершини, які є частиною дерева найкоротшого шляху (SPT), а інша - вершини, які оцінюються для включення до SPT. Отже, для кожної ітерації ми знаходимо вершину з другого списку, яка має найкоротший шлях.

Псевдокод алгоритму найкоротшого шляху Дейкстри наведено нижче.

Запити sql беруть інтерв’ю на запитання та відповіді за 3-річний досвід

Псевдокод

Нижче наведено псевдокод для цього алгоритму.

procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end

Давайте тепер візьмемо зразковий графік та проілюструємо алгоритм найкоротшого шляху Дейкстри .

алгоритм найкоротшого шляху

Спочатку для набору SPT (Shortest Path Tree) встановлено нескінченність.

Почнемо з вершини 0. Отже, для початку ми помістимо вершину 0 у sptSet.

sptSet = {0, INF, INF, INF, INF, INF}.

Далі з вершиною 0 у sptSet ми дослідимо її сусідів. Вершини 1 і 2 - це два сусідні вузли 0 з відстанню 2 і 1 відповідно.

сусідні вузли

На наведеному малюнку ми також оновили кожну сусідню вершину (1 і 2) з відповідною відстанню від вихідної вершини 0. Тепер ми бачимо, що вершина 2 має мінімальну відстань. Отже, ми додаємо вершину 2 до sptSet. Крім того, ми досліджуємо сусідів вершини 2.

сусідня вершина

Тепер ми шукаємо вершину з мінімальною відстанню і ті, яких немає в spt. Вибираємо вершину 1 з відстанню 2.

вершина з мінімальною відстанню

Як ми бачимо на наведеному малюнку, із усіх сусідніх вузлів 2, 0 та 1 вже є у sptSet, тому ми їх ігноруємо. З сусідніх вузлів 5 і 3 5 мають найменшу вартість. Тож ми додаємо його до sptSet та досліджуємо сусідні вузли.

сусідні вузли 2, 0

На наведеному малюнку ми бачимо, що крім вузлів 3 і 4, всі інші вузли знаходяться в sptSet. З 3 та 4 вузол 3 має найменшу вартість. Тож ми помістили його в sptSet.

вузли 3 і 4

Як показано вище, тепер у нас залишилася лише одна вершина, тобто 4, і її відстань від кореневого вузла дорівнює 16. Нарешті, ми поміщаємо її в sptSet, щоб отримати кінцевий sptSet = {0, 2, 1, 5, 3, 4}, що дає нам відстань кожної вершини від вихідного вузла 0.

Впровадження алгоритму Дейкстри в Java

Реалізація найкоротшого алгоритму Дейкстри в Java може бути досягнута двома способами. Ми можемо використовувати черги пріоритетів та список суміжностей, а також матрицю сусідства та масиви.

У цьому розділі ми побачимо обидві реалізації.

Використання черги пріоритетів

У цій реалізації ми використовуємо чергу пріоритетів для зберігання вершин з найменшою відстанню. Графік визначається за допомогою списку суміжностей. Зразок програми наведено нижче.

import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i

Вихід:

черга пріоритетів - вихід

Використання матриці суміжності

У цьому підході ми використовуємо матрицю суміжності для представлення графіка. Для набору spt ми використовуємо масиви.

Наступна програма показує цю реалізацію.

import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v

Вихід:

Матриця суміжності - вихід

Часті запитання

Q # 1) Чи працює Дейкстра для неорієнтованих графіків?

Відповідь: Якщо графік спрямований чи ненаправлений, це не має значення у випадку алгоритму Дейкстри. Цей алгоритм стосується лише вершин на графіку та ваг.

Q # 2) Яка часова складність алгоритму Дейкстри?

Відповідь: Складність часу Алгоритму Дейкстри дорівнює O (V 2). При реалізації з чергою з мінімальним пріоритетом часова складність цього алгоритму зводиться до O (V + E l o g V).

Q # 3) Чи Дейкстра є жадібним алгоритмом?

Відповідь: Так, Дейкстра - це жадібний алгоритм. Подібно алгоритму Прима для пошуку мінімального охоплюючого дерева (MST), ці алгоритми також починаються з кореневої вершини і завжди вибирають найбільш оптимальну вершину з мінімальним шляхом.

Q # 4) Дійкстра DFS чи BFS?

Відповідь: Це ні те, ні інше. Але оскільки алгоритм Дейкстри використовує пріоритетну чергу для своєї реалізації, його можна розглядати як близький до BFS.

Q # 5) Де використовується алгоритм Дейкстри?

Відповідь: Він використовується переважно в протоколах маршрутизації, оскільки допомагає знайти найкоротший шлях від одного вузла до іншого.

Висновок

У цьому підручнику ми обговорили алгоритм Дейкстри. Ми використовуємо цей алгоритм, щоб знайти найкоротший шлях від кореневого вузла до інших вузлів у графіку або дереві.

Зазвичай ми реалізуємо алгоритм Дейкстри за допомогою черги пріоритетів, оскільки нам потрібно знайти мінімальний шлях. Ми також можемо реалізувати цей алгоритм, використовуючи матрицю суміжності. Ми обговорили обидва ці підходи в цьому посібнику.

Ми сподіваємось, що цей підручник буде вам корисним.

=> Завітайте сюди, щоб побачити навчальну серію Java для всіх

Рекомендована література

^