Coder Forum

Java Quellcode

import java.util.*;
import fhw.ADSTool;
 
/**
 * Aufgabe2:
 * Berechnet den kuerzesten Weg zwischen 2 Knoten
 * @author Torben Brodt & Marco May
 *
 */
public class A2 {
 
/**
 * Mainmethode
 * @param args - Kommandozeilenparameter
 */
	public static void main(String[] args) {
		Graph g = new Graph();
		String[] werte = ADSTool.readStringArray(args.length == 0 ? "u12a2entf.dat" : args[0]);
		String start = args.length == 0 ? "Frankfurt/Main" : args[1];
		String ende = args.length == 0 ? "Augsburg" : args[2];
 
		for (int i = 0; i < werte.length - 2; i += 3) {
			if (!g.containsNode(werte[i])) // Stadt1
				g.addNode(werte[i]);
 
			if (!g.containsNode(werte[i + 1])) // Stadt2
				g.addNode(werte[i + 1]);
 
			if(!g.containsEdge(werte[i + 1], werte[i]))
				g.addDoubleEdge(werte[i + 1], werte[i], Integer.parseInt(werte[i + 2]));
		}
 
//g.show();
		System.out.println(shortestPath(g,start,ende));		
 
	}
 
 
	/**
	 * Berechnet die k�rzeste Strecke zwischen Start und Zielpunkt
	 * Anmerk.: In Zusammenarbeit mit Jarek Janas
	 * @param g	- Erstellter Graph
	 * @param start	-Startstring
	 * @param ziel -Zielstring
	 * @return Liste der gegangenen Knoten
	 */
	private static List<String> shortestPath(Graph g, String start, String ziel) {
		Heap myHeap = new Heap(g, start);
 
List<String> l = new LinkedList<String>();
 
 
		while (!myHeap.getSmallestNode().equals(ziel) && myHeap.getDistance(myHeap.getSmallestNode()) != Integer.MAX_VALUE) { 
 
 
			String stadtname =  myHeap.getSmallestNode();
			int wegZuDieserStadt = myHeap.getDistance(stadtname);
			int naechsterWert, val;
 
			myHeap.deleteNode(stadtname);
 
			for (Iterator<String> eit = g.edgeIterator(stadtname); eit.hasNext() ;) { 
				//Von dieser Stadt werden alle verknuepften Staedte geladen (bzw. Knoten wird expandiert)
				//Die Edges/Values werden verglichen und der kuerzeste Weg gesucht
				String verbundeneStadt = eit.next(); //Stuttgart Mannheim
 
				val = g.getEdgeValue(stadtname, verbundeneStadt);
				naechsterWert= wegZuDieserStadt + val;
 
 
				//in der PQ sind alle staedte drinne, also wird hier nur der wert bearbeitet
				//bearbeiten = loeschen und neu einfuegen (die PQ wird dann automatisch neu sortiert)
				//Update der Distanz nur, wenn ein besserer Weg gefunden wurde
 
				if(naechsterWert < myHeap.getDistance(verbundeneStadt)) {//kuerzerer Weg gefunden?
 
					myHeap.deleteNode(verbundeneStadt);
					myHeap.add(verbundeneStadt, naechsterWert);
					l.add(stadtname);
					l.add(verbundeneStadt);
				}
//				System.out.println("verbundene Stadt=>"+verbundeneStadt+" mit Wert "+naechsterWert);
 
				if(verbundeneStadt.equals(ziel)) {
					String[] arr = new String[l.size()];
					int myI = l.size();
					for(Iterator<String> myit=l.iterator(); myit.hasNext(); ) {
						arr[--myI] = myit.next(); //from
						arr[--myI] = myit.next(); //to
					}
 
					l = rekAusgabe(arr, 0, ziel, start, g, new LinkedList<String>());
					System.out.println("Kuerzester Weg von "+start+" nach "+ziel+" in "+myHeap.getDistance(ziel));
					return l;
				}
			}			
 
		}
		return null; //Keine Route
	}
 
	/**
	 * Rekursive Ausgabe der besuchten Punkte in eine Liste
	 * @param arr	- Ausgangsarray mit den besuchten Punkten
	 * @param i	-Monentaner Standpunkt
	 * @param ziel	-Zielknoten
	 * @param start	-Startknoten
	 * @param g	-Graphen
	 * @param l	-Liste in die gespeichert wird
	 * @return
	 */
	private static List<String> rekAusgabe(String[] arr, int i,String ziel, String start, Graph g, List<String> l) {
		if(i<arr.length && arr[i].equals(start)) {
			return l;
		}
		for(i=0; i<arr.length; i+=2) {
			if(arr[i].equals(ziel)) {
				int val = g.getEdgeValue(arr[i],arr[i+1]);
				l.add(0, arr[i+1]+" -> "+ziel+"("+val+")");
				return rekAusgabe(arr, i+1, arr[i+1], start, g,l);
			}
		}
		return null;
	}
}

Java Quellcode

package ueb911;
import java.util.*;
 
/**
 * Heapklasse zum Verwalten der PQ
 * 
 */
public class Heap {
	Queue<Node> queue = new PriorityQueue<Node>();
	Map<String, Integer> map = new HashMap<String, Integer>();
 
	/**
	 * Konstruktor Start Knoten mit 0 init. /alle anderen sind unendlich
	 * @param g
	 * @return
	 */
	public Heap(Graph g, String start) {
		Iterator <String> it = g.nodeIterator();
 
		while(it.hasNext()) {
			String node = it.next();
			if(node.equals(start)){
				queue.add(new Node(node,0));
				map.put(node, 0);
			}
			else{
				queue.add(new Node(node,Integer.MAX_VALUE));
				map.put(node, Integer.MAX_VALUE);
			}
		}
	}
 
	/**
	 * Knotenklasse, wird intern verwaltet
	 * mit Knotenname und Wert
	 */
	class Node implements Comparable {
		String node, prev;
		int wert;
 
		public Node (String node, int distance) {
			this.node = node;
			this.wert = distance;
		}
 
		public int compareTo(Object o) {
			if (this.wert > ((Node)o).wert) return 1;
			if (this.wert < ((Node)o).wert) return -1;
			else return 0;
		}
	} 
 
	/**
	 * Fügt Knoten hinzu
	 * @param node -akt. Knoten
	 * @param wert-akt. Wert
	 */
	public void add(String node, int wert) {
		queue.add(new Node(node, wert));
		map.put(node, wert);
	}
 
	/**
	 * Gibt die Entfernung eines Knotens
	 * @return Distanz
	 */
	public String getSmallestNode() {
		return queue.peek().node;
	}
 
	/**
	 * Gibt die Entfernung eines Knotens
	 * @return Distanz
	 */
	public int getDistance(String node) {
		return map.get(node);
	}
 
	/**
	 * Löscht den Knoten aus dem Heap
	 * @param node -zu löschender Knoten
	 */
	public void deleteNode(String node) {
		queue.remove(new Node(node, map.get(node)));
	}
}