Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Kürzester Weg (Kleinprojekte)

In der folgenden Grafik bezeichnen die Kreise Ortschaften und die Linien dazwischen sind Straßen, welche die Ortschaften verbinden.

Jeder Ort ist mit einem Buchsaben von A bis Z bezeichnet. Bei jeder Straße steht eine Zahl, welche angibt, wie viele Kilometer die entsprechenden Städte auseinander liegen.

Schreiben Sie nun ein Programm, bei dem die Autofahrerin Start- und Zielort eingeben kann (also zwei Buchstaben). Das Programm findet nun den kürzesten Weg zwischen den beiden Ortschaften und gibt die Gesamtlänge, sowie alle besuchten Orte aus.

 

Landkarte

Um Ihnen das mühselige Abtippen zu schenken, sind die Abstände nochmals in der folgenden Tabelle angegeben:

von nach Abstand
A B 6
A D 7
B C 4
B E 4
C F 6
C I 8
D G 5
E J 5
F K 5
G H 5
G I 7
H L 5
I M 5
J K 7
J T 4
K U 9
L M 6
M N 5
N O 7
O Q 5
P Q 8
P U 2
Q X 7
R T 8
R Y 10
R Z 4
S W 2
S X 4
T V 7
W Y 9
X Y 11

Tipp: Der Informatiker Edsger Dijkstra hat hierzu einen Algorithmus angegeben. Obschon er selbst wusste, dass sein Algorithmus für sehr große Problemstellungen nicht mehr optimal ist, so können wir für unsere 26 Ortschaften sehr gut auch den nach ihm benannten Algorithmus verwenden.

2 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (2)

gressly 3. Februar 2015 12:04   reply report
Tobias_Petri
Sollte in der Checksumme für die Strecke "A"-"Z" nicht 31 stehen?

Stimmt.
Das Resultat habe ich korrigiert.
Da war auch noch ein Fehler in meinem Programm in der Klasse Landkarte in der Funktion unbesuchterOrtMitMinimalabstand().

Sollte nun korrekt sein.
Tobias_Petri 2. Februar 2015 19:13   reply report
Sollte in der Checksumme für die Strecke "A"-"Z" nicht 31 stehen?

2 Lösung(en)

package ch.programmieraufgaben.kleinprojekte.kuerzesterweg;

/* input: see here https://github.com/pheek/javaInput/blob/master/Input.java */
import static eu.gressly.io.utility.Input.inputChar;
/**
 * Programmieraufgabe finde minimalen Weg
 * @version 0.1 (Jan 23, 2015)
 * @author Philipp Gressly Freimann 
 *         (philipp.gressly@santis.ch)
 */
public class Dijkstra {

	public static void main(String[] args) {
		try {
			new Dijkstra().top();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	void top() throws Exception {
		Landkarte landkarte = Landkarte.initGraph();
		char startOrt = inputChar("Startort (A-Z):");
		landkarte.getOrt(startOrt).setzeVorgaenger('\u0000');
		landkarte.getOrt(startOrt).setzeWeglaenge(0);
		while(landkarte.hatUnbesuchteOrte()) {
			Ort minOrt = landkarte.unbesuchterOrtMitMinimalabstand();
			minOrt.besucht = true;
			for(Ort angrenzend: landkarte.angrenzendeAn(minOrt)) {
				behandleNachbar(landkarte, minOrt, angrenzend);
			}
			//System.out.println("Debug in top(): minOrt besucht: " + minOrt);
		}
		// ende: Ausgabe
		char zielOrt = inputChar("Zielort (A-Z): ");
		int weglaenge = landkarte.liesWegLaenge(zielOrt);
		ausgabeAlleWege(landkarte, startOrt, zielOrt, weglaenge);
	}

	private void ausgabeAlleWege(Landkarte landkarte, char startOrt, char zielOrt, int weglaenge) {
		System.out.println("Die Weglänge zum Zielort " + zielOrt + " ist " + weglaenge);
		Ort o = landkarte.getOrt(zielOrt);
		System.out.println("Unterwegs wurden besucht: ");
		while(o.name != startOrt) {
			System.out.println(o.name);
			o = landkarte.getOrt(o.vorgaenger);
		}
		System.out.println(startOrt);
	}


	private void behandleNachbar(Landkarte landkarte, Ort minOrt, Ort angrenzend) {
		int ortAbstand = ortAbstand(minOrt, angrenzend);
		if(Math.abs(minOrt.weglaenge - angrenzend.weglaenge) > ortAbstand) {
			updateWeiterenVonBeiden(minOrt, angrenzend, ortAbstand);
		}
	}

	private void updateWeiterenVonBeiden(Ort minOrt, Ort angrenzend,
			int ortAbstand) {
		Ort naeher, weiter;
		if(minOrt.weglaenge <= angrenzend.weglaenge) {
			naeher = minOrt;
			weiter = angrenzend;
		} else {
			naeher = angrenzend;
			weiter = minOrt;
		}
		weiter.weglaenge = naeher.weglaenge + ortAbstand;
		weiter.vorgaenger = naeher.name;
	}


	private int ortAbstand(Ort minOrt, Ort angrenzend) {
		for(Weg w : minOrt.wege) {
			if(w.ortA == angrenzend.name || w.ortB == angrenzend.name) {
				return w.weglaenge;
			}
		}
		return Integer.MAX_VALUE;
	}
}
 // end of class Dijkstra

//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////

package ch.programmieraufgaben.kleinprojekte.kuerzesterweg;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


/**
 * Hilfsklasse für "Finde Kürzesten Weg"
 * @version 0.1 (Jan 23, 2015)
 * @author Philipp Gressly Freimann 
 *         (philipp.gressly@santis.ch)
 */
public class Landkarte {
	public static String CSV_FILE_NAME = "src/ch/programmieraufgaben/kleinprojekte/kuerzesterweg/karte.csv";
	
	Map<Character, Ort> ortMenge = new HashMap<Character, Ort>();
	/**
	 * TODO Document Method
	 * @return
	 */
	public static Landkarte initGraph() throws Exception {
		Landkarte l = new Landkarte();
		FileReader fr = new FileReader(CSV_FILE_NAME);
		String line = null;
		BufferedReader br = new BufferedReader(fr);
		while(null != (line = br.readLine())) {
			String[] args = line.split(",");
			char ortA = args[0].charAt(0);
			char ortB = args[1].charAt(0);
			int  abst = Integer.parseInt(args[2].trim());
			ensureOrt(l, ortA);
			ensureOrt(l, ortB);
			l.ortMenge.get(ortA).addWeg(ortB, abst);
			l.ortMenge.get(ortB).addWeg(ortA, abst);
		}
		br.close();
		return l;
	}
	
	private static void ensureOrt(Landkarte l, char ort) {
		if(l.ortMenge.containsKey(ort)) {
			return;
		}
		Ort o = new Ort(ort);
		o.vorgaenger =                 0;
		o.wege       = null             ;
		o.weglaenge  = Integer.MAX_VALUE; 
		l.ortMenge.put(ort, o);
	}


	public Ort getOrt(char startOrt) {
		return this.ortMenge.get(startOrt);
	}


	public boolean hatUnbesuchteOrte() {
		for(Ort o : ortMenge.values()) {
			if(!o.besucht) {
				return true;
			}
		}
		return false;
	}


	public Ort unbesuchterOrtMitMinimalabstand() {
		Ort resultat = null;
		int  minAbst  = Integer.MAX_VALUE;
		for(Ort o: ortMenge.values()) {
			if(! o.besucht) {
				if(null == resultat) {
					resultat = o;
                                        minAbst = o.weglaenge;
				} else {
					if(minAbst > o.weglaenge) {
						resultat = o;
						minAbst  = o.weglaenge;
					}
				}
			}
		}
		return resultat;
	}


	public List<Ort> angrenzendeAn(Ort minOrt) {
		ArrayList<Ort> angrenzende = new ArrayList<Ort>();
		for(Ort o: ortMenge.values()) {
			if(minOrt != o) {
				for(Weg w : o.wege) {
					if(w.ortA == minOrt.name || w.ortB == minOrt.name) {
						angrenzende.add(o);
					}
				}
			}
		}
		return angrenzende;
	}

	/**
	 * TODO Document Method
	 * @param zielOrt
	 */
	public int liesWegLaenge(char zielOrt) {
		return ortMenge.get(zielOrt).weglaenge;
	}


} // end of class Landkarte

///////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////


package ch.programmieraufgaben.kleinprojekte.kuerzesterweg;

import java.util.Set;
import java.util.TreeSet;


public class Ort {
	char      name      ;
	char      vorgaenger;
	int       weglaenge ;
	Set<Weg>  wege      ;
	boolean   besucht   ;
	
	@Override
	public String toString() {
		return "Ort " + name + " (Vorgänger: " + (0 == vorgaenger ? "[]" : vorgaenger) + ") [weglänge total von start aus: " + weglaenge + "] <besucht: " + besucht + ">"; 
	}
	
	public Ort(char name) {
		this.name       = name              ;
		this.vorgaenger =                  0;
		this.weglaenge  = Integer.MAX_VALUE ;
		this.wege       = new TreeSet<Weg>();
		besucht         = false             ;
	}

	public void addWeg(char ortB, int abst) {
		if(null == wege) {
			wege = new TreeSet<Weg>();
		}
		Weg w = new Weg();
		w.ortA = this.name;
		w.ortB = ortB;
		w.weglaenge = abst;
		wege.add(w);
	}

	public void setzeVorgaenger(char vorgaenger) {
		this.vorgaenger = vorgaenger;
	}


	public void setzeWeglaenge(int weglaenge) {
		this.weglaenge = weglaenge;
	}

} // end of class Ort

////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////


package ch.programmieraufgaben.kleinprojekte.kuerzesterweg;


/**
 * Weg für die "Minimale Weglänge" Programmierübung
 * @version 0.1 (Jan 23, 2015)
 * @author Philipp Gressly Freimann 
 *         (philipp.gressly@santis.ch)
 */
public class Weg implements Comparable<Weg> {
	char ortA;
	char ortB;
	int  weglaenge;

	/* compareTo, because used in a java-Set */
	@Override
	public int compareTo(Weg o) {
		if(this.ortA != o.ortA) {
			return o.ortA - this.ortA;
		}
		if(this.ortB != o.ortB){
			return o.ortB - this.ortB;
		}
		return o.weglaenge - this.weglaenge;
	}

} // end of class Weg

//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////


A,B,6
A,D,7
B,C,4
B,E,4
C,F,6
C,I,8
D,G,5
E,J,5
F,K,5
G,H,5
G,I,7
H,L,5
I,M,5
J,K,7
J,T,4
K,U,9
L,M,6
M,N,5
N,O,7
O,Q,5
P,Q,8
P,U,2
Q,X,7
R,T,8
R,Y,10
R,Z,4
S,W,2
S,X,4
T,V,7
W,Y,9
X,Y,11
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

/***
 Kürzester Weg Algorithmus
 http://www.programmieraufgaben.ch/aufgabe/kuerzester-weg/inybyc9q
 
 Es wird basierend auf der vorgegebenen Karte zunächst einmalig eine Knotenstruktur
 aus Objekten (gewichteter Graph) angelegt, in der für jeden Knoten seine Nachbarn
 und die Entfernungen zu ihnen hinterlegt sind.
 Hiernach wird bei jedem Aufruf mit einer Kopie dieser Daten der Dijkstra Algorithmus
 durchlaufen.
 Vgl. Psodocode von: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
 
 Der Algorithmus muss von der Console oder aus dem html mit dem Aufruf:
 >>>	Dijkstra.go('<Name Startort>','<Name Zielort>');
 gestartet werden. Das Ergebnis wird in der Console in Tabellenformat ausgegeben.
 (Browser: FF, Chrome, javascript-Standard ab ie9)

 Lösung von Tobias Petri, 2.2.2015, Graz
***/

// Objekt-array für Karte erzeugen:
var karte = 'A:B:6;A:D:7;B:C:4;B:E:4;C:F:6;C:I:8;D:G:5;E:J:5;F:K:5;G:H:5;G:I:7;H:L:5;I:M:5;J:K:7;J:T:4;K:U:9;L:M:6;M:N:5;N:O:7;O:Q:5;P:Q:8;P:U:2;Q:X:7;R:T:8;R:Y:10;R:Z:4;S:W:2;S:X:4;T:V:7;W:Y:9;X:Y:11'
		.split(';').map(function(n){ return n.split(':')})
		.map(function(n){ return {stadt1:n[0],stadt2:n[1],dist:parseInt(n[2])}});

var Dijkstra = (function(){
	var d = {},
	  knoten = [], startKnoten, zielKnoten,
	  // objekt-funktion zur initialisierung der Knoten:
	  neuKnoten = function(n) { var k={}; k.name = n; k.distSum = Number.MAX_VALUE; k.vorg = null; k.nachbn = []; return k; }
	
	initKnoten();
	d.go = function(startName, zielName){
		resetKnoten();
		// startknoten, zielknoten aus Parametern zuweisen:
		// (alternativ hier prompt und keine Parameter...)
		knoten.forEach(function(k){
			if (k.name === startName){ startKnoten = k; k.distSum = 0; }
			if (k.name === zielName){ zielKnoten = k;}
		});
		if (!startKnoten) { alert('Startort konnte nicht gefunden werden!'); return; }
		if (!zielKnoten)  { alert('Zielort konnte nicht gefunden werden!'); return; }

		runDijkstra();
		makePfad();
	}

	function resetKnoten(){
		// (Bei wiederoltem Aufruf müssen die Nachbarn nicht erneut initialisiert werden.)
		knoten.forEach(function(k){
			k.distSum = Number.MAX_VALUE;
			k.vorg = null;
		});
		startKnoten = null;
		zielKnoten = null;
	}
	
	function initKnoten(){ // (einmaliger Aufruf)
		karte.forEach(function(stadt){
			// Städenamen aus Verbindungentabelle in Knoten-Liste aufnehmen:
			// (für jede Stadt nur einen Knoten anlegen!)
			if (!knoten.some(function(k){ return k.name === stadt.stadt1})){
				knoten.push(neuKnoten(stadt.stadt1))
			}
			if (!knoten.some(function(k){ return k.name === stadt.stadt2})){
				knoten.push(neuKnoten(stadt.stadt2))
			}
		});
		// Nachbarn aus Karte mit Entfernungsangaben (kar.dist) den Knoten hinzufügen:
		var kartenNachbarn;
		knoten.forEach(function(kno){
			knoten.forEach(function(knoNb){
				// Karte nach Orten duchsuchen:
				karte.forEach(function(kar){
					if (  (kar.stadt1 === kno.name &&  kar.stadt2 === knoNb.name)
					    ||(kar.stadt2 === kno.name &&  kar.stadt1 === knoNb.name)){
						kno.nachbn.push({nKnot:knoNb, nDist:kar.dist});
					}
				});
			});
		});
	}
	
	function runDijkstra(){
		var kAct, knotenPool = Array.concat(knoten);
		while (knotenPool.length){
			kAct = getLowestDistK(knotenPool);

			if (kAct === zielKnoten) { return kAct; }

			kAct.nachbn.forEach(function(n){
				// wenn Entfernung zwischen beiden Städten + bisher erreichte kleiner ist,
				// diese dem Nachbarknoten als Wert (distSum) übergeben und sein Vorgänger (neu) zuweisen:
				if (kAct.distSum + n.nDist < n.nKnot.distSum){
					n.nKnot.distSum = kAct.distSum + n.nDist;
					n.nKnot.vorg = kAct;
				}
			});
		}
	}
		
	function getLowestDistK(knotenPool){
		var dMin = Number.MAX_VALUE, kDmin = null, ikDmin;
		knotenPool.forEach(function(k, i){
			if (k.distSum < dMin) {
				kDmin = k;
				dMin = k.distSum;
				ikDmin = i;
			}
		});
		// Knoten mit kürzester Entfernung aus Pool entnehmen und zurückgeben:
		return knotenPool.splice(ikDmin,1)[0];
	}

	function makePfad(){
		var pfad = [], kvorg;
		// Vom Zielknoten ausgehend den Pfad zurückverfolgen:
		pfad[0] = kvorg = zielKnoten;
		while (kvorg.vorg){
			kvorg = kvorg.vorg;
			// Vorgänger am Anfang einfügen:
			pfad.unshift(kvorg);
		}
		console.table(pfad);
	}
	
	return d;
})()
                

Lösung von: Tobias Petri (energie graz)

Verifikation/Checksumme:

Startort (A-Z): A
Zielort (A-Z): Z
Die Weglänge zum Zielort Z ist 31
Unterwegs wurden besucht:
Z-R-T-J-E-B-A

Startort (A-Z): H
Zielort (A-Z): T
Die Weglänge zum Zielort T ist 36
Unterwegs wurden besucht:
T-J-E-B-A-D-G-H

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 8
Schwierigkeit: Schwer
Webcode: inyb-yc9q
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen