Java Routenplanung: Dijkstra

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Java Routenplanung: Dijkstra

    Quellcode

    1. import java.util.*;
    2. import fhw.ADSTool;
    4. /**
    5. * Aufgabe2:
    6. * Berechnet den kuerzesten Weg zwischen 2 Knoten
    7. * @author Torben Brodt & Marco May
    8. *
    9. */
    10. public class A2 {
    12. /**
    13. * Mainmethode
    14. * @param args - Kommandozeilenparameter
    15. */
    16. public static void main(String[] args) {
    17. Graph g = new Graph();
    18. String[] werte = ADSTool.readStringArray(args.length == 0 ? "u12a2entf.dat" : args[0]);
    19. String start = args.length == 0 ? "Frankfurt/Main" : args[1];
    20. String ende = args.length == 0 ? "Augsburg" : args[2];
    22. for (int i = 0; i < werte.length - 2; i += 3) {
    23. if (!g.containsNode(werte[i])) // Stadt1
    24. g.addNode(werte[i]);
    26. if (!g.containsNode(werte[i + 1])) // Stadt2
    27. g.addNode(werte[i + 1]);
    29. if(!g.containsEdge(werte[i + 1], werte[i]))
    30. g.addDoubleEdge(werte[i + 1], werte[i], Integer.parseInt(werte[i + 2]));
    31. }
    33. //g.show();
    34. System.out.println(shortestPath(g,start,ende));
    36. }
    39. /**
    40. * Berechnet die k�rzeste Strecke zwischen Start und Zielpunkt
    41. * Anmerk.: In Zusammenarbeit mit Jarek Janas
    42. * @param g - Erstellter Graph
    43. * @param start -Startstring
    44. * @param ziel -Zielstring
    45. * @return Liste der gegangenen Knoten
    46. */
    47. private static List<String> shortestPath(Graph g, String start, String ziel) {
    48. Heap myHeap = new Heap(g, start);
    50. List<String> l = new LinkedList<String>();
    53. while (!myHeap.getSmallestNode().equals(ziel) && myHeap.getDistance(myHeap.getSmallestNode()) != Integer.MAX_VALUE) {
    56. String stadtname = myHeap.getSmallestNode();
    57. int wegZuDieserStadt = myHeap.getDistance(stadtname);
    58. int naechsterWert, val;
    60. myHeap.deleteNode(stadtname);
    62. for (Iterator<String> eit = g.edgeIterator(stadtname); eit.hasNext() ;) {
    63. //Von dieser Stadt werden alle verknuepften Staedte geladen (bzw. Knoten wird expandiert)
    64. //Die Edges/Values werden verglichen und der kuerzeste Weg gesucht
    65. String verbundeneStadt = eit.next(); //Stuttgart Mannheim
    67. val = g.getEdgeValue(stadtname, verbundeneStadt);
    68. naechsterWert= wegZuDieserStadt + val;
    71. //in der PQ sind alle staedte drinne, also wird hier nur der wert bearbeitet
    72. //bearbeiten = loeschen und neu einfuegen (die PQ wird dann automatisch neu sortiert)
    73. //Update der Distanz nur, wenn ein besserer Weg gefunden wurde
    75. if(naechsterWert < myHeap.getDistance(verbundeneStadt)) {//kuerzerer Weg gefunden?
    77. myHeap.deleteNode(verbundeneStadt);
    78. myHeap.add(verbundeneStadt, naechsterWert);
    79. l.add(stadtname);
    80. l.add(verbundeneStadt);
    81. }
    82. // System.out.println("verbundene Stadt=>"+verbundeneStadt+" mit Wert "+naechsterWert);
    84. if(verbundeneStadt.equals(ziel)) {
    85. String[] arr = new String[l.size()];
    86. int myI = l.size();
    87. for(Iterator<String> myit=l.iterator(); myit.hasNext(); ) {
    88. arr[--myI] = myit.next(); //from
    89. arr[--myI] = myit.next(); //to
    90. }
    92. l = rekAusgabe(arr, 0, ziel, start, g, new LinkedList<String>());
    93. System.out.println("Kuerzester Weg von "+start+" nach "+ziel+" in "+myHeap.getDistance(ziel));
    94. return l;
    95. }
    96. }
    98. }
    99. return null; //Keine Route
    100. }
    102. /**
    103. * Rekursive Ausgabe der besuchten Punkte in eine Liste
    104. * @param arr - Ausgangsarray mit den besuchten Punkten
    105. * @param i -Monentaner Standpunkt
    106. * @param ziel -Zielknoten
    107. * @param start -Startknoten
    108. * @param g -Graphen
    109. * @param l -Liste in die gespeichert wird
    110. * @return
    111. */
    112. private static List<String> rekAusgabe(String[] arr, int i,String ziel, String start, Graph g, List<String> l) {
    113. if(i<arr.length && arr[i].equals(start)) {
    114. return l;
    115. }
    116. for(i=0; i<arr.length; i+=2) {
    117. if(arr[i].equals(ziel)) {
    118. int val = g.getEdgeValue(arr[i],arr[i+1]);
    119. l.add(0, arr[i+1]+" -> "+ziel+"("+val+")");
    120. return rekAusgabe(arr, i+1, arr[i+1], start, g,l);
    121. }
    122. }
    123. return null;
    124. }
    125. }
    Alles anzeigen
    Dateien

    • Graph.java

      (6,81 kB, 1.351 mal heruntergeladen, zuletzt: )

    • GraphException.java

      (297 Byte, 899 mal heruntergeladen, zuletzt: )

  • Anbei noch die fehlende Heap Implementierung

    Quellcode

    1. package ueb911;
    2. import java.util.*;
    4. /**
    5. * Heapklasse zum Verwalten der PQ
    6. *
    7. */
    8. public class Heap {
    9. Queue<Node> queue = new PriorityQueue<Node>();
    10. Map<String, Integer> map = new HashMap<String, Integer>();
    12. /**
    13. * Konstruktor Start Knoten mit 0 init. /alle anderen sind unendlich
    14. * @param g
    15. * @return
    16. */
    17. public Heap(Graph g, String start) {
    18. Iterator <String> it = g.nodeIterator();
    20. while(it.hasNext()) {
    21. String node = it.next();
    22. if(node.equals(start)){
    23. queue.add(new Node(node,0));
    24. map.put(node, 0);
    25. }
    26. else{
    27. queue.add(new Node(node,Integer.MAX_VALUE));
    28. map.put(node, Integer.MAX_VALUE);
    29. }
    30. }
    31. }
    33. /**
    34. * Knotenklasse, wird intern verwaltet
    35. * mit Knotenname und Wert
    36. */
    37. class Node implements Comparable {
    38. String node, prev;
    39. int wert;
    41. public Node (String node, int distance) {
    42. this.node = node;
    43. this.wert = distance;
    44. }
    46. public int compareTo(Object o) {
    47. if (this.wert > ((Node)o).wert) return 1;
    48. if (this.wert < ((Node)o).wert) return -1;
    49. else return 0;
    50. }
    51. }
    53. /**
    54. * Fügt Knoten hinzu
    55. * @param node -akt. Knoten
    56. * @param wert-akt. Wert
    57. */
    58. public void add(String node, int wert) {
    59. queue.add(new Node(node, wert));
    60. map.put(node, wert);
    61. }
    63. /**
    64. * Gibt die Entfernung eines Knotens
    65. * @return Distanz
    66. */
    67. public String getSmallestNode() {
    68. return queue.peek().node;
    69. }
    71. /**
    72. * Gibt die Entfernung eines Knotens
    73. * @return Distanz
    74. */
    75. public int getDistance(String node) {
    76. return map.get(node);
    77. }
    79. /**
    80. * Löscht den Knoten aus dem Heap
    81. * @param node -zu löschender Knoten
    82. */
    83. public void deleteNode(String node) {
    84. queue.remove(new Node(node, map.get(node)));
    85. }
    86. }
    Alles anzeigen