Aus ProgrammingWiki

Inhaltsverzeichnis

1 Unbewertete Graphen
- 1.1 Übung 1.1
- 1.2 Übung 1.2
2 Übung Kürzeste Wege in bewerteten Graphen
3 Lösungen

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.

Darstellung Graph G anzeigen

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