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

      (6,81 kB, 950 mal heruntergeladen, zuletzt: )
    • GraphException.java

      (297 Byte, 517 mal heruntergeladen, zuletzt: )
  • Anbei noch die fehlende Heap Implementierung

    Quellcode

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