Übung Kürzeste Wege in Graphen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=Flo Teil=
<language>Java</language>
=Ü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) und 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>
===Lösungen===
<popup name="Aufgabe 2.1">[[Bild:Alpreu_Auk1-u.png]]</popup>