Übung Kürzeste Wege in Graphen

Wiki-Quelltext dieser Seite.

=Flo Teil=
=Kürzeste Wege in bewerteten Graphen=

===Übung 2.1===
Führen Sie den Dijkstra-Algorithmus per Hand für folgende Graphendarstellung aus.
Legen Sie dazu eine Tabelle an.
<popup name="Darstellung Graph G">[[Bild:Alpreu_Auk1.png]]</popup>

===Übung 2.2===
Implementieren Sie den Floyd-Algorithmus in einer Programmiersprache Ihrer Wahl.
Lesen Sie dazu eine Matrix ein (alternativ: im Quelltext hardcoden) und wenden Sie den Algorithmus an.
Geben Sie die Ergebnismatrix aus.
Testen Sie ihren Algorithmus mit folgenden Matrizen:

===Übung 2.3===
Machen Sie sich selbstständig mit verschiedenen Datenstrukturen und ihren Vor-/Nachteilen
für die verschiedenen Algorithmen vertraut. (Bsp. Fibonacci-Heap)

===Übung 2.4===
Machen Sie sich mit weiteren Algorithmen zur Bestimmung des kürzesten Weges vertraut.
Welche Unterschiede weisen diese auf? (Bsp. A*-Algorithmus, Bellman-Ford-Algorithmus)

<language>Java</language>
===Übung 2.5===
Vervollständigen Sie die Implementierung des Dijkstra-Algorithmus.
Fügen Sie dazu die folgende Klassen in ihre IDE ein.
<code id="5642148bac7bf">
public class Vertex {

	final private String id;
	final private String name;


	public Vertex(String id, String name) {
		this.id = id;
		this.name = name;
	}
	
	public String getId() {
		return id;
	}

	public String getName() {
		return name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((id == null) ? 0 : id.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Vertex other = (Vertex) obj;
		if (id == null) {
			if (other.id != null)
				return false;
		} else if (!id.equals(other.id))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return name;
	}

}
</code>
<code>
public class Edge {
	private final String id; 
	private final Vertex source;
	private final Vertex destination;
	private final int weight; 

	public Edge(String id, Vertex source, Vertex destination, int weight) {
		this.id = id;
		this.source = source;
		this.destination = destination;
		this.weight = weight;
	}

	public String getId() {
		return id;
	}
	
	public Vertex getDestination() {
		return destination;
	}

	public Vertex getSource() {
		return source;
	}
	
	public int getWeight() {
		return weight;
	}

	@Override
	public String toString() {
		return source + " " + destination;
	}
}
</code>

===Lösungen===
<popup name="Aufgabe 2.1">[[Bild:Alpreu_Auk1-u.png]]</popup>