Dijkstra-Algoritmus

Susi123

Aktives Mitglied
Meine Aufgabe lautet folgendermaßen:
Berechnen Sie mit dem Algorithmus von Dijkstra den kürzesten Weg von S zu jedem anderen
Knoten. Dokumentieren Sie den Verlauf in einer Doppel-Tabelle.
Hinweis: Falls zwei Knoten in der Warteschlange die gleiche Distanz von S haben, wählen Sie bitte
den mit dem kleineren Index zuerst, also zum Beispiel F4 vor F6.

1583862799075.png

Habe ich bei folgender Lösung den Algorithmus richtig verstanden?

1583862907934.png

Vielleicht kann mir jemand dabei helfen. Vielen Dank im Voraus.

 

LimDul

Top Contributor
Mit so einer Tabelle hab ich nie gearbeitet. Die Zahlen sehen auf jeden Fall richtig aus und die Arbeitungsreihenfolge der Knoten sieht auch gut aus (hab es jetzt nicht im Detail geprüft).

Was mich aber wundert, in der zweiten Zeile auf der Rechten Seite. Warum da bei F1 schon F3 drin? Ich nehme an dass in der Zelle am Ende der jeweilige Vorgängerknoten drin steht um den Knoten auf dem kürzesten Weg zu erreichen. Zu diesem Zeitpunkt - also im ersten Durchlauf - weiß ich aber doch noch nicht, dass ich F1 am schnellsten über F3 erreiche. Zu diesem Zeitpunkt weiß ich doch nur, dass ich F1 von S mit den Kosten 3 erreiche. Daher hätte ich erwartet, dass noch dort S drinsteht und erst in der dritten Zeile sich das zu F3 ändert.
 
X

Xyz1

Gast
Also diese völlig ineffiziente Implementierung gibt mir Folgendes aus
Java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

import com.google.common.graph.EndpointPair;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

public class Test {
	private static class E implements Comparable<E> {
		String s;
		E e;
		int x;

		E(String s, int x) {
			this.s = s;
			this.x = x;
		}

		public int compareTo(E o) {
			return x - o.x;
		}

		@Override
		public String toString() {
			if (e == null) {
				return String.format("[s=%s, x=%s]", s, x);
			} else {
				return String.format("[e=%s, s=%s, x=%s]", e.toString(), s, x);
			}
		}
	}

	public static void dijkstra(MutableValueGraph<String, Integer> graph) {
		Set<EndpointPair<String>> edges = graph.edges();
		HashSet<String> ready = new HashSet<String>();
		ArrayList<Test.E> queue = new ArrayList<Test.E>();
		for (String s : graph.nodes()) {
			if (s.equals("S")) {
				queue.add(new E(s, 0));
			} else {
				queue.add(new E(s, 1000));
			}
		}
		Collections.sort(queue);
		while (!queue.isEmpty()) {
			boolean updated = false;
			E e = queue.remove(0);
			ready.add(e.s);

			System.out.println(e);

			for (EndpointPair<String> p : edges) {
				if (p.nodeU().equals(e.s) && !ready.contains(p.nodeV())) {
					int v = e.x + graph.edgeValue(p).get();
					for (E e2 : queue) {
						if (e2.s.equals(p.nodeV())) {
							if (v < e2.x) {
								e2.x = v;
								e2.e = e;
								updated = true;
							}
							break;
						}
					}
				}
			}
			if (updated) {
				Collections.sort(queue);
			}
		}
	}

	public static void main(String[] args) {
		MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed().build();
		graph.addNode("S");
		graph.addNode("F1");
		graph.addNode("F2");
		graph.addNode("F3");
		graph.addNode("F4");
		graph.addNode("F5");
		graph.addNode("F6");
		graph.putEdgeValue("S", "F1", 3);
		graph.putEdgeValue("S", "F3", 1);
		graph.putEdgeValue("F1", "F2", 4);
		graph.putEdgeValue("F1", "F4", 2);
		graph.putEdgeValue("F3", "F1", 1);
		graph.putEdgeValue("F3", "F5", 2);
		graph.putEdgeValue("F4", "F5", 1);
		graph.putEdgeValue("F5", "F6", 1);
		graph.putEdgeValue("F6", "F2", 1);
		dijkstra(graph);
	}
}

Code:
[s=S, x=0]
[e=[s=S, x=0], s=F3, x=1]
[e=[e=[s=S, x=0], s=F3, x=1], s=F1, x=2]
[e=[e=[s=S, x=0], s=F3, x=1], s=F5, x=3]
[e=[e=[e=[s=S, x=0], s=F3, x=1], s=F1, x=2], s=F4, x=4]
[e=[e=[e=[s=S, x=0], s=F3, x=1], s=F5, x=3], s=F6, x=4]
[e=[e=[e=[e=[s=S, x=0], s=F3, x=1], s=F5, x=3], s=F6, x=4], s=F2, x=5]

Deine Tabelle scheint richtig zu sein ;)
 
X

Xyz1

Gast
Hier nochmal etwas effizienter aber noch nicht zu 100 % perfekt (siehe Anmerkung(en) mit //):
Java:
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

import com.google.common.graph.EndpointPair;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

public class Test {
	private static class E implements Comparable<E> {
		String s;
		E e;
		int x;

		E(String s, int x) {
			this.s = s;
			this.x = x;
		}

		public int compareTo(E o) {
			return x - o.x;
		}

		/* We don't really need this...
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((s == null) ? 0 : s.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;
			E other = (E) obj;
			if (s == null) {
				if (other.s != null)
					return false;
			} else if (!s.equals(other.s))
				return false;
			return true;
		}
		*/

		@Override
		public String toString() {
			if (e == null) {
				return String.format("[s=%s, x=%s]", s, x);
			} else {
				return String.format("[e=%s, s=%s, x=%s]", e.toString(), s, x);
			}
		}
	}

	public static void dijkstra(MutableValueGraph<String, Integer> graph) {
		Set<EndpointPair<String>> edges = graph.edges();
		HashSet<String> ready = new HashSet<String>();
		PriorityQueue<Test.E> queue = new PriorityQueue<Test.E>();
		HashMap<String, Test.E> queue2 = new HashMap<String, Test.E>();
		for (String s : graph.nodes()) {
			if (s.equals("S")) {
				E e = new E(s, 0);
				queue.add(e);
				queue2.put(s, e);
			} else {
				E e = new E(s, 1000);
				queue.add(e);
				queue2.put(s, e);
			}
		}

		while (!queue.isEmpty()) {
			E e = queue.poll();
			ready.add(e.s);

			System.out.println(e);

			for (EndpointPair<String> p : edges) { // This costs time...
				if (p.nodeU().equals(e.s) && !ready.contains(p.nodeV())) {
					int v = e.x + graph.edgeValue(p).get();
					E e2 = queue2.get(p.nodeV());
					if (v < e2.x) {
						e2.x = v;
						e2.e = e;
						queue.remove(e2);
						queue.add(e2);
					}
				}
			}
		}

		System.out.println();
		for (E e : queue2.values()) {
			System.out.println(e);
		}
	}

	public static void main(String[] args) {
		MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed().build();
		graph.addNode("S");
		graph.addNode("F1");
		graph.addNode("F2");
		graph.addNode("F3");
		graph.addNode("F4");
		graph.addNode("F5");
		graph.addNode("F6");
		graph.putEdgeValue("S", "F1", 3);
		graph.putEdgeValue("S", "F3", 1);
		graph.putEdgeValue("F1", "F2", 4);
		graph.putEdgeValue("F1", "F4", 2);
		graph.putEdgeValue("F3", "F1", 1);
		graph.putEdgeValue("F3", "F5", 2);
		graph.putEdgeValue("F4", "F5", 1);
		graph.putEdgeValue("F5", "F6", 1);
		graph.putEdgeValue("F6", "F2", 1);
		dijkstra(graph);
	}
}

BTW: 1000 ist ein willkürlicher Wert das kann schnell das Ergebnis verfälschen wenn es zum Beispiel um Meter geht...
 
X

Xyz1

Gast
Ich weiß gar nicht genau, wo was wie ausgegeben werden sollte (in welchem Schritt), weil ich die Tabelle nicht genau versteh. Das ist mehr oder weniger Interpretationssache des Lehrkörpers. Dijkstra gehört aber zum Standardreportai eines jeden Info-Studenten. Ich kann mich daran erinnern, in einer Prüfung auch so eine Tabelle ausfüllen zu müssen. Allerdings ist das wie gesagt immer vorlesungsbezogen auszufüllen...

/e Standardrepertoire
 

Ähnliche Java Themen

Neue Themen


Oben