streamalism.org

1. Áttekintés

Ebben a cikkben a hangsúly a legrövidebb út problémája (SPP), amely a gráfelméletben ismert egyik alapvető elméleti probléma, és hogy miként lehet a Dijkstra algoritmust megoldani.

Az algoritmus alapvető célja a kezdő csomópont és a grafikon többi része közötti legrövidebb út meghatározása.

2. A legrövidebb út probléma a Dijkstrával

Pozitívan súlyozott gráfot és egy kezdő csomópontot (A) adva Dijkstra meghatározza a legrövidebb utat és távolságot a forrástól a grafikon összes céljáig:

A Dijkstra algoritmus alapötlete az, hogy folyamatosan kiküszöbölje a hosszabb utakat a kiinduló csomópont és az összes lehetséges cél között.

A folyamat nyomon követéséhez két külön csomópont-készletre van szükségünk, telepített és rendezetlen.

A letelepedett csomópontok ismertek a minimális távolsággal a forrástól. A rendezetlen csomópontok olyan csomópontokat gyűjtenek, amelyeket elérhetünk a forrásból, de nem ismerjük a minimális távolságot a kezdő csomóponttól.

Az alábbiakban felsoroljuk az SPP Dijkstrával való megoldása érdekében követendő lépéseket:

• Állítsa be a távolságot startNode nullára.
• Állítsa az összes többi távolságot végtelen értékre.
• Hozzáadjuk a startNode a meg nem rendezett csomópontokra.
• Bár a beállítatlan csomópontok nem üresek, mi:
  • Válasszon kiértékelő csomópontot a beállítatlan csomópontok közül, az értékelési csomópont legyen az, amelynek a legkisebb távolsága van a forrástól.
  • Számítson ki új távolságokat a közvetlen szomszédokhoz úgy, hogy az egyes értékeléseknél a legkisebb távolságot tartja.
  • Adja hozzá a még rendezetlen szomszédokat a beállítatlan csomópontokhoz.

Ezeket a lépéseket két szakaszba lehet összesíteni: az inicializálás és az értékelés. Lássuk, ez hogyan vonatkozik a minta grafikonunkra:

2.1. Inicializálás

Mielőtt elkezdenénk felfedezni a grafikon összes útját, először inicializálnunk kell az összes végtelen távolságú és ismeretlen előddel rendelkező csomópontot, a forrás kivételével.

Az inicializálási folyamat részeként 0 értéket kell rendelnünk az A csomóponthoz (tudjuk, hogy az A csomópont és az A csomópont távolsága nyilvánvalóan 0)

Tehát a gráf többi részében lévő minden csomópont meg lesz különböztetve egy előddel és egy távolsággal:

Az inicializálási folyamat befejezéséhez hozzá kell adnunk az A csomópontot a rendezetlen csomópontokhoz, és állítsuk be azt az első lépésként az értékelési lépésben. Ne feledje, hogy a beállított csomópontok még mindig üresek.

2.2. Értékelés

Most, hogy gráfunkat inicializáltuk, kiválasztjuk azt a csomópontot, amelynek a legkisebb távolsága van a rendezetlen halmaztól, majd kiértékeljük az összes szomszédos csomópontot, amelyek nincsenek letelepedett csomópontokban:

Az ötlet az, hogy hozzáadjuk az él súlyát az értékelési csomópont távolságához, majd összehasonlítjuk azt a cél távolságával. például. a B csomópont esetében a 0 + 10 alacsonyabb, mint az INFINITY, tehát a B csomópont új távolsága 10, az új előd pedig A, ugyanez vonatkozik a C csomópontra is.

Az A csomópont ezután a beállított rendezetlen csomópontokról a letelepített csomópontokra kerül.

A B és C csomópontok hozzáadódnak a rendezetlen csomópontokhoz, mert elérhetõk, de ki kell értékelni.

Most, hogy két csomópontunk van a rendezetlen halmazban, kiválasztjuk a legkisebb távolságú csomópontot (B csomópont), majd addig ismételjük, amíg a csomópontokat el nem rendezzük a grafikonon:

Az alábbi táblázat összefoglalja az értékelési lépések során végrehajtott iterációkat:

A B-22 jelölés például azt jelenti, hogy a B csomópont a közvetlen előd, az A csomópont teljes távolsága 22.

Végül kiszámíthatjuk a legrövidebb utakat az A csomópontból:

• B csomópont: A -> B (teljes távolság = 10)
• C csomópont: A -> C (teljes távolság = 15)
• D csomópont: A -> B -> D (teljes távolság = 22)
• E csomópont: A -> B -> D -> E (teljes távolság = 24)
• F csomópont: A -> B -> D -> F (teljes távolság = 23)

3. Java implementáció

Ebben az egyszerű megvalósításban a gráfot csomópontok halmazaként jelenítjük meg:

public class Graph {private Set csomópontok = new HashSet (); public void addNode (Node nodeA) {csomópontok.add (csomópontA); } // szerelők és beállítók}

Egy csomópont leírható az a-val név, a LinkedList hivatkozva a shortestPath, a távolság a forrásból, és egy megnevezett szomszédsági lista szomszédos csomópontok:

public class Csomópont {private String name; private List shortestPath = új LinkedList (); privát egész távolság = Integer.MAX_VALUE; Térkép szomszédosNodes = új HashMap (); public void addDestination (Csomópont célállomása, int távolság) {szomszédosNodes.put (cél, távolság); } public Node (karakterlánc neve) {this.name = név; } // szerelők és beállítók}

A szomszédos csomópontok attribútum a közvetlen szomszédok élhosszal való társítására szolgál. Ez egy szomszédsági lista egyszerűsített megvalósítása, amely jobban megfelel a Dijkstra algoritmusnak, mint a szomszédsági mátrixnak.

Ami a shortestPath attribútum, ez a csomópontok listája, amely leírja a kezdő csomóponttól számított legrövidebb utat.

Alapértelmezés szerint az összes csomópont távolságot inicializáljuk Egész.MAX_VALUE végtelen távolság szimulálására az inicializálási lépésben leírtak szerint.

Most valósítsuk meg a Dijkstra algoritmust:

nyilvános statikus grafikon calcShortestPathFromSource (Grafikon grafikon, Csomópont forrás) {source.setDistance (0); Set settNodes = új HashSet (); Set unsettledNodes = new HashSet (); unsettledNodes.add (forrás); while (rendezetlenNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); for (Entry adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {Csomópont szomszédosNode = adjacencyPair.getKey (); Egész szám edgeWeight = adjacencyPair.getValue (); if (! SettNodes.contains (szomszédosNode)) {{kiszámoljaMinimumDistance (szomszédosNode, edgeWeight, currentNode); unsettledNodes.add (szomszédos csomópont); }} SettNodes.add (currentNode); } visszatérési grafikon; }

A getLowestDistanceNode () metódussal adja vissza a beállított csomópontoktól a legkisebb távolságú csomópontot, míg a calcMinimumDistance () módszer összehasonlítja a tényleges távolságot az újonnan kiszámított távolsággal, miközben követi az újonnan feltárt utat:

privát statikus csomópont getLowestDistanceNode (Set unsettledNodes) {Csomópont legalDistanceNode = null; int legkisebb távolság: Integer.MAX_VALUE; for (Csomópont csomópont: rendezetlen csomópontok) {int csomópontTávolság = csomópont.getDistance (); if (nodeDistance <legkisebbDistance) {legalDistance = nodeDistance; legalDistanceNode = csomópont; }} return minimumDistanceNode; }

privát statikus void CalculateMinimumDistance (Node assessmentNode, Integer edgeWeigh, Node sourceNode) {Integer sourceDistance = sourceNode.getDistance (); if (sourceDistance + edgeWeigh <assessmentNode.getDistance ()) {assessmentNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = új LinkedList (sourceNode.getShortestPath ()); shortestPath.add (forrásNode); assessmentNode.setShortestPath (shortestPath); }}

Most, hogy minden szükséges darab a helyén van, alkalmazzuk a Dijkstra algoritmust a cikk tárgyát képező mintagrafikonon:

Csomópont csomópontA = új csomópont ("A"); Csomópont csomópontB = új csomópont ("B"); Csomópont csomópontC = új csomópont ("C"); Csomópont csomópontD = új csomópont ("D"); Csomópont csomópontE = új csomópont ("E"); Csomópont csomópontF = új csomópont ("F"); nodeA.addDestination (csomópont B, 10); nodeA.addDestination (nodeC, 15); nodeB.addDestination (nodeD, 12); nodeB.addDestination (csomópont F, 15); nodeC.addDestination (nodeE, 10); nodeD.addDestination (nodeE, 2); nodeD.addDestination (nodeF, 1); nodeF.addDestination (nodeE, 5); Grafikondiagram = new Graph (); graph.addNode (csomópont A); graph.addNode (nodeB); graph.addNode (nodeC); graph.addNode (nodeD); graph.addNode (nodeE); graph.addNode (nodeF); graph = Dijkstra.calculateShortestPathFromSource (gráf, csomópont A); 

Számítás után a shortestPath és távolság az attribútumok a csomópont minden egyes csomópontjához vannak beállítva, ezeken keresztül iterálhatunk, hogy ellenőrizzük, hogy az eredmények pontosan megfelelnek-e az előző szakaszban találtaknak.

4. Következtetés

Ebben a cikkben láthattuk, hogyan oldja meg a Dijkstra algoritmus az SPP-t, és hogyan valósíthatja meg azt a Java-ban.

Ennek az egyszerű projektnek a megvalósítása megtalálható a következő GitHub projekt linken.