Übung Kürzeste Wege in Graphen

Aus ProgrammingWiki

Archivierte Version vom 2015-11-14T10:15:52+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Unbewertete Graphen
- 1.1 Übung 1.1
- 1.2 Übung 1.2
2 Übung Kürzeste Wege in bewerteten Graphen

Unbewertete Graphen

Übung 1.1

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

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.

Hinweis: Dieses Problem ist auch als "Taxigeometrie" bekannt.

Übung 1.2

Finden Sie den kürzesten Weg mittels Breitensuche oder mit "Scharfem Hinsehen". 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.

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

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

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

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

}

Testen Sie den Algorithmus auf Funktionsfähigkeit mithilfe der folgenden JUnit Test Klasse:

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

Übung Kürzeste Wege in Graphen

Inhaltsverzeichnis

Unbewertete Graphen

Übung 1.1

Übung 1.2

Übung Kürzeste Wege in bewerteten Graphen

Übung 2.1

Übung 2.2

Übung 2.3

Übung 2.4

Übung 2.5*

Lösungen

Suche