Übung Kürzeste Wege in Graphen

Aus ProgrammingWiki

Archivierte Version vom 2015-11-10T16:02:02+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Flo Teil
2 Kürzeste Wege in bewerteten Graphen

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.

Ü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)

Übung 2.5

Vervollständigen Sie die Implementierung des Dijkstra-Algorithmus. Fügen Sie dazu die folgende Klassen in ihre IDE ein.

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;
	}

}

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;
	}
}

Übung Kürzeste Wege in Graphen

Inhaltsverzeichnis

Flo Teil

Kürzeste Wege in bewerteten Graphen

Übung 2.1

Übung 2.2

Übung 2.3

Übung 2.4

Übung 2.5

Lösungen

Suche