Algorytm najkrótszej ścieżki Dijkstry w Javie

1. Przegląd

W tym artykule położono nacisk na problem najkrótszej ścieżki (SPP), będący jednym z fundamentalnych problemów teoretycznych znanych w teorii grafów, oraz sposób wykorzystania algorytmu Dijkstry do jego rozwiązania.

Podstawowym celem algorytmu jest wyznaczenie najkrótszej ścieżki między węzłem początkowym a resztą wykresu.

2. Problem najkrótszej ścieżki z Dijkstrą

Biorąc pod uwagę dodatnio ważony wykres i węzeł początkowy (A), Dijkstra określa najkrótszą ścieżkę i odległość od źródła do wszystkich miejsc docelowych na wykresie:

Podstawową ideą algorytmu Dijkstry jest ciągłe eliminowanie dłuższych ścieżek między węzłem początkowym a wszystkimi możliwymi miejscami docelowymi.

Aby śledzić ten proces, potrzebujemy dwóch odrębnych zestawów węzłów, ustalonych i nierozliczonych.

Węzły osiadłe to te, które mają znaną minimalną odległość od źródła. Zestaw węzłów nierozliczonych gromadzi węzły, do których możemy dotrzeć ze źródła, ale nie znamy minimalnej odległości od węzła początkowego.

Oto lista kroków, które należy wykonać, aby rozwiązać SPP za pomocą Dijkstry:

  • Ustaw odległość do startNode na zero.
  • Ustaw wszystkie inne odległości na nieskończoną wartość.
  • Dodajemy startNode do zestawu nierozliczonych węzłów.
  • Podczas gdy zestaw węzłów nierozliczonych nie jest pusty, my:
    • Wybierz węzeł oceny z zestawu węzłów nierozliczonych, węzłem oceny powinien być ten z najmniejszą odległością od źródła.
    • Oblicz nowe odległości do bezpośrednich sąsiadów, zachowując najmniejszą odległość przy każdej ocenie.
    • Dodaj sąsiadów, którzy nie są jeszcze rozliczeni, do zestawu węzłów nierozliczonych.

Kroki te można łączyć w dwa etapy: inicjalizację i ocenę. Zobaczmy, jak to się ma do naszego przykładowego wykresu:

2.1. Inicjalizacja

Zanim zaczniemy eksplorować wszystkie ścieżki na grafie, musimy najpierw zainicjować wszystkie węzły z nieskończoną odległością i nieznanym poprzednikiem, z wyjątkiem źródła.

W ramach procesu inicjalizacji musimy przypisać wartość 0 do węzła A (wiemy, że odległość od węzła A do węzła A wynosi oczywiście 0)

Tak więc każdy węzeł w pozostałej części wykresu zostanie wyróżniony poprzednikiem i odległością:

Aby zakończyć proces inicjalizacji, musimy dodać węzeł A do węzłów nierozliczonych, ustawiając go tak, aby był wybierany jako pierwszy w kroku oceny. Pamiętaj, że zestaw rozliczonych węzłów jest nadal pusty.

2.2. Ocena

Po zainicjowaniu naszego wykresu wybieramy węzeł znajdujący się w najmniejszej odległości od zbioru nierozliczonego, a następnie oceniamy wszystkie sąsiednie węzły, które nie znajdują się w węzłach ustalonych:

Chodzi o to, aby dodać wagę krawędzi do odległości węzła oceny, a następnie porównać ją z odległością celu. np. dla węzła B 0 + 10 jest mniejsze niż INFINITY, więc nowa odległość dla węzła B wynosi 10, a nowy poprzednik to A, to samo dotyczy węzła C.

Węzeł A jest następnie przenoszony z węzłów nierozliczonych do ustalonych węzłów.

Węzły B i C są dodawane do węzłów nierozliczonych, ponieważ można do nich dotrzeć, ale muszą zostać ocenione.

Teraz, gdy mamy dwa węzły w nierozliczonym zbiorze, wybieramy ten z najmniejszą odległością (węzeł B), a następnie powtarzamy, aż ustalimy wszystkie węzły na wykresie:

Oto tabela podsumowująca iteracje, które zostały wykonane podczas etapów oceny:

Iteracja Zaburzony Osiadły EvaluationNode ZA b do re mi fa
1 ZA - ZA 0 A-10 A-15 X-∞ X-∞ X-∞
2 PNE ZA b 0 A-10 A-15 B-22 X-∞ B-25
3 C, F, D A, B do 0 A-10 A-15 B-22 C-25 B-25
4 D, E, F. A, B, C re 0 A-10 A-15 B-22 D-24 D-23
5 E, F. A, B, C, D fa 0 A-10 A-15 B-22 D-24 D-23
6 mi A, B, C, D, F. mi 0 A-10 A-15 B-22 D-24 D-23
Finał - WSZYSTKO ŻADEN 0 A-10 A-15 B-22 D-24 D-23

Na przykład notacja B-22 oznacza, że ​​węzeł B jest bezpośrednim poprzednikiem, z całkowitą odległością 22 od węzła A.

Wreszcie możemy obliczyć najkrótsze ścieżki z węzła A w następujący sposób:

  • Węzeł B: A -> B (całkowita odległość = 10)
  • Węzeł C: A -> C (całkowita odległość = 15)
  • Węzeł D: A -> B -> D (całkowita odległość = 22)
  • Węzeł E: A -> B -> D -> E (całkowita odległość = 24)
  • Węzeł F: A -> B -> D -> F (całkowita odległość = 23)

3. Implementacja Java

W tej prostej implementacji przedstawimy wykres jako zbiór węzłów:

public class Graph { private Set nodes = new HashSet(); public void addNode(Node nodeA) { nodes.add(nodeA); } // getters and setters }

A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:

public class Node { private String name; private List shortestPath = new LinkedList(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } // getters and setters }

The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.

As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.

By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.

Now, let's implement the Dijkstra algorithm:

public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(0); Set settledNodes = new HashSet(); Set unsettledNodes = new HashSet(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry  adjacencyPair: currentNode.getAdjacentNodes().entrySet()) { Node adjacentNode = adjacencyPair.getKey(); Integer edgeWeight = adjacencyPair.getValue(); if (!settledNodes.contains(adjacentNode)) { calculateMinimumDistance(adjacentNode, edgeWeight, currentNode); unsettledNodes.add(adjacentNode); } } settledNodes.add(currentNode); } return graph; }

The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:

private static Node getLowestDistanceNode(Set  unsettledNodes) { Node lowestDistanceNode = null; int lowestDistance = Integer.MAX_VALUE; for (Node node: unsettledNodes) { int nodeDistance = node.getDistance(); if (nodeDistance < lowestDistance) { lowestDistance = nodeDistance; lowestDistanceNode = node; } } return lowestDistanceNode; }
private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) { Integer sourceDistance = sourceNode.getDistance(); if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) { evaluationNode.setDistance(sourceDistance + edgeWeigh); LinkedList shortestPath = new LinkedList(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } }

Now that all the necessary pieces are in place, let's apply the Dijkstra algorithm on the sample graph being the subject of the article:

Node nodeA = new Node("A"); Node nodeB = new Node("B"); Node nodeC = new Node("C"); Node nodeD = new Node("D"); Node nodeE = new Node("E"); Node nodeF = new Node("F"); nodeA.addDestination(nodeB, 10); nodeA.addDestination(nodeC, 15); nodeB.addDestination(nodeD, 12); nodeB.addDestination(nodeF, 15); nodeC.addDestination(nodeE, 10); nodeD.addDestination(nodeE, 2); nodeD.addDestination(nodeF, 1); nodeF.addDestination(nodeE, 5); Graph graph = new Graph(); graph.addNode(nodeA); graph.addNode(nodeB); graph.addNode(nodeC); graph.addNode(nodeD); graph.addNode(nodeE); graph.addNode(nodeF); graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA); 

Po obliczeniu atrybuty shortestPath i distance są ustawiane dla każdego węzła na wykresie, możemy je iterować, aby sprawdzić, czy wyniki dokładnie pasują do tego, co znaleziono w poprzedniej sekcji.

4. Wniosek

W tym artykule widzieliśmy, jak algorytm Dijkstra rozwiązuje SPP i jak zaimplementować go w Javie.

Implementację tego prostego projektu można znaleźć w następującym linku do projektu GitHub.