Übung Kürzeste Wege in Graphen

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Unbewertete Graphen=
===Übung 1.1===
<p>Überlegen Sie, wie viele verschiedene kürzeste Wege es in einem "Manhatten-Graphen" mit neun, sechzehn, fünfundzwanzig oder beliebig vielen Knoten gibt. Finden Sie so viele Wege wie möglich und versuchen sie, eine allgemeine Lösung (eine systematische Aufzählung oder eine allgemeine Formel) zu finden.</p>
[[Bild:Manhattengraph_5x5.PNG]]
<p>Hinweis: Die Anzahl der kürzesten Wege von einem beliebigen Punkt zum Endpunkt ist gleich der Summe der kürzesten Wege von den beiden Knoten, die als erster Schritt in Frage kommen.</p>
<p>Hinweis: Dieses Problem ist auch als "Taxigeometrie" bekannt.</p>

===Übung 1.2===
Finden Sie den kürzesten Weg mittels Breitensuche oder mit "Scharfem Hinsehen".
[[Bild:Flhaje_unberwerteter Graph.PNG]]
Hinweis: Der kürzeste Weg hat eine Länge von 8.

=Übung 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) 
*Wenden Sie den Algorithmus an.
*Geben Sie die Ergebnismatrix aus.
*Um ihren Algorithmus zu testen können Sie [https://www.cs.usfca.edu/~galles/visualization/Floyd.html hier] Eingabematrizen und die korrekte Ausgabematrix generieren.

===Ü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 Charakteristiken und Unterschiede weisen diese auf? (Bsp. A*-Algorithmus, Bellman-Ford-Algorithmus)

===Ü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 id="564217213f09f">
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 id="564217213f12b">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 id="564217213f1a3">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>
*Testen Sie den Algorithmus auf Funktionsfähigkeit mithilfe der folgenden JUnit Test Klasse:
<code id="564217213f226">import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class TestDijkstraAlgorithm {

  private List<Vertex> nodes;
  private List<Edge> edges;

  @Test
  public void testExcute() {
    nodes = new ArrayList<Vertex>();
    edges = new ArrayList<Edge>();
    for (int i = 0; i < 11; i++) {
      Vertex location = new Vertex("Node_" + i, "Node_" + i);
      nodes.add(location);
    }

    addLane("Edge_0", 0, 1, 85);
    addLane("Edge_1", 0, 2, 217);
    addLane("Edge_2", 0, 4, 173);
    addLane("Edge_3", 2, 6, 186);
    addLane("Edge_4", 2, 7, 103);
    addLane("Edge_5", 3, 7, 183);
    addLane("Edge_6", 5, 8, 250);
    addLane("Edge_7", 8, 9, 84);
    addLane("Edge_8", 7, 9, 167);
    addLane("Edge_9", 4, 9, 502);
    addLane("Edge_10", 9, 10, 40);
    addLane("Edge_11", 1, 10, 600);

    // Lets check from location Loc_1 to Loc_10
    Graph graph = new Graph(nodes, edges);
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
    dijkstra.execute(nodes.get(0));
    LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10));
    
    assertNotNull(path);
    assertTrue(path.size() > 0);
    
    for (Vertex vertex : path) {
      System.out.println(vertex);
    }
    
  }

  private void addLane(String laneId, int sourceLocNo, int destLocNo,
      int duration) {
    Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration);
    edges.add(lane);
  }
} 


</code>

<language>Java</language>
==Lösungen==
<popup name="Aufgabe 2.1">[[Bild:Alpreu_Auk1-u.png]]</popup>
<popup name="Aufgabe 2.2">Aufgrund der Formatierung sieht man nur einen Teil des Codes in der Box.
Mit Cursor in der Box und Strg-A öffnet sich die Codebox und man sieht den gesamten Code.
<code id="5647091dea435">

public class FloydAlgorithm {

	
	//Damit nicht verbundene Knoten nicht mitberechnet werden hohen Wert als Platzhalter nehmen
	final static int INF = 1000; //1000 reicht hier, ansonsten z.B. MaxInteger nehmen
	

	//Eingabematrix
	static int a[][] = {{0, 8, INF,1},
						{INF,0,1, INF},
						{4,INF,0, INF},
						{INF,2, 9, 0}};  
	
	//Ergebnismatrix
	static int d[][] = new int [4][4]; 

	public static void main(String argv[]) {
		int N=a.length; //Knotenzahl

		//Schritt 1, Kopie der Eingabematrix in Ergebnismatrix
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				d[i][j] = a[i][j];
			}
		}

		//Schritt 2, Bestimmen der kürzesten Wege
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					d[i][j] = java.lang.Math.min(d[i][j], (d[i][k]+d[k][j]));
				}
			}
		}

		//Schritt 3, Druck der Ergebnismatrix
		for (int x= 0; x< N; x++) {
			for (int y= 0; y< N; y++) {
				if(d[x][y] == INF){
					System.out.print(" INF"); //für einheitliche Darstellung
				}else{
					System.out.print(" "+d[x][y]);
				}
			}
			System.out.println();
		}
	}
}
</code></popup>
<popup name="Aufgabe 2.3">Eine gute [http://lak.informatik.uni-freiburg.de/lak_teaching/ws10_11/slides/07-fibonacci-heaps.pdf Präsentation] zum Nachvollziehen der Komplexitätsunterschiede</popup>
<popup name="Aufgabe 2.4">
===Bellman-Ford-Algorithmus===
* Richard Bellman, Lester Ford Jr.  
* SSSP-Algorithmus
* langsamer als Dijkstra-Algorithmus angewendet auf gleichen Graphen, '''aber'''
* kann mit negativen Kantenbewertungen arbeiten 
* erkennt negative Zyklen 
* <math>O(|V|\cdot |E|)</math>
** $|V|$: Anzahl der Knoten, $|E|$: Anzahl der Kanten

===A*-Algorithmus===
* Peter Hart, Nils J. Nilsson, Bertram Raphael
* weit verbreitet aufgrund der guten Performance (z.B.: Pathfinding in Videospielen)
* kann als Erweiterung des Dijkstra-Algorithmus betrachtet werden
* verwendet Heuristik um Laufzeit zu verringern
* Die Komplextität hängt vom Erfolg der Heuristik ab
* Im schlechtesten Fall beträgt sie <math>O(|V|^2)</math>
** $|V|$: Anzahl Knoten
</popup>