Ü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===
*Fügen Sie die folgende Klassen in ihre IDE ein.
*Vervollständigen Sie die Klasse DijkstraAlgorithm mithilfe des in Kommentaren angegebenen Pseudocodes.
<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>
<code>import java.util.List;


public class Graph {
	private final List<Vertex> vertexes;
	private final List<Edge> edges;

	public Graph(List<Vertex> vertexes, List<Edge> edges) {
		this.vertexes = vertexes;
		this.edges = edges;
	}

	public List<Vertex> getVertexes() {
		return vertexes;
	}

	public List<Edge> getEdges() {
		return edges;
	}
}
</code>
<code>import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class DijkstraAlgorithm {

	private final List<Vertex> nodes;
	private final List<Edge> edges;
	private Set<Vertex> settledNodes;
	private Set<Vertex> unSettledNodes;
	private Map<Vertex, Vertex> predecessors;
	private Map<Vertex, Integer> distance;

	
	public DijkstraAlgorithm(Graph graph) {	
		this.nodes = new ArrayList<Vertex>(graph.getVertexes());
		this.edges = new ArrayList<Edge>(graph.getEdges());
	}

	public void execute(Vertex source) {
		settledNodes = new HashSet<Vertex>();
		unSettledNodes = new HashSet<Vertex>();
		distance = new HashMap<Vertex, Integer>();
		predecessors = new HashMap<Vertex, Vertex>();
		
		
		/*
		 	distance[sourceNode]= 0
			Add sourceNode to UnSettledNodes
			while (UnSettledNodes is not empty) {
  				evaluationNode = getNodeWithLowestDistance(UnSettledNodes)
  				remove evaluationNode from UnSettledNodes 
    			add evaluationNode to SettledNodes
    			findMinimalDistances(evaluationNode)
    		}
    		
		 */
		
	}

	private void findMinimalDistances(Vertex node) {
		List<Vertex> adjacentNodes = getNeighbors(node);
		
		/*
		   run throught the vertexes in adjacentNodes{
		   	 if(getShortestDistance(vertex) > getShortestDistance(vertex)+getDistance(node, vertex)){
		   	 	add the vertex and getShortestDistance(node) + getDistance(node, vertex) to distance
		   	 	add vertex, node to predecessors
		   	 	add vertex to unSettledNodes
		   	 }	  
		   } 
		   
		*/
		

	}

	private int getDistance(Vertex node, Vertex target) {
		for (Edge edge : edges) {
			if (edge.getSource().equals(node)
					&& edge.getDestination().equals(target)) {
				return edge.getWeight();
			}
		}
		throw new RuntimeException("Should not happen");
	}

	private List<Vertex> getNeighbors(Vertex node) {
		
		
		/**/
		
		List<Vertex> neighbors = new ArrayList<Vertex>();
		for (Edge edge : edges) {
			if (edge.getSource().equals(node)
					&& !isSettled(edge.getDestination())) {
				neighbors.add(edge.getDestination());
			}
		}
		return neighbors;
	}

	private Vertex getNodeWithLowestDistance(Set<Vertex> vertexes) {
		Vertex minimum = null;
		/* run through the set of vertexes{
			if(minimum is null){ set it to the current vertex}
		  	else{
		  		  if (getShortestDistance(vertex) < getShortestDistance(minimum)){
		  			set minimum to the current vertex
		          }
		        }
		   }
		 */

		 return minimum;		
		
	}

	private boolean isSettled(Vertex vertex) {
		return settledNodes.contains(vertex);
	}

	private int getShortestDistance(Vertex destination) {
		Integer d = distance.get(destination);
		if (d == null) {
			return Integer.MAX_VALUE;
		} else {
			return d;
		}
	}

	
	public LinkedList<Vertex> getPath(Vertex target) {
		LinkedList<Vertex> path = new LinkedList<Vertex>();
		Vertex step = target;
		// checks if a path exists, dont change anything here
		if (predecessors.get(step) == null) {
			return null;
		}
		path.add(step);
		while (predecessors.get(step) != null) {
			step = predecessors.get(step);
			path.add(step);
		}
		// Puts it into the correct order, dont change anything here
		Collections.reverse(path);
		return path;
	}

}
</code>

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