matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieWegfindung im Graphen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Wegfindung im Graphen
Wegfindung im Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Wegfindung im Graphen: Finden von Alternativwegen
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 22:28 So 01.12.2013
Autor: Parano.Oya

Aufgabe
Gegeben ist ein beliebiger schlichter, ungerichteter, gewichteter Graph G.
Dabei ist G zusammenhängend und weder ein Baum noch ein Kreis.
Mit dem Algorithmus von Dijkstra kann der kürzeste Weg vom Startpunkt zum Zielpunkt errechnet werden. Zu finden sind nun, falls existent, alle Alternativwege des Graphen G.


Guten Abend an die Community,

um es kurz zu fassen: Die Aufgabenstellung bezieht sich auf eine spätere Implementierung in einem Programm unter C++. Die Implementierung ist für mich nun keine großartige Hürde. Die Aufgabe selbst ist schon zum größten Teil erfüllt. Dies ist im Übrigen keine Hausaufgabe oder so ein Spaß.
Das wohl wichtigste Problem ist wohl die Überlegung des Ganzen...

Aber eins nach dem anderen. Wir haben einen beliebigen Graphen G mit den obigen Eigenschaften. Ich arbeite als angehender Informatiker nun, was die Darstellung der Graphen betrifft, mit einer Adjazenz-Matrix. Aus der Adjazenz-Matrix erstelle ich eine Binärmatrix. Anhand der Binärmatrix ist eindeutig zu erkennen, wie hoch der Grad des Startpunktes und des Zielpunktes ist.

Mein Ziel ist es nun alle Alternativwege, falls existent, im Graphen G zu finden. Ich bin daher wie folgt vorgegangen: In jedem Schritt entferne ich eine Kante vom Startpunkt, sofern der Grad vom SP > 1 ist, errechne mittels dem Algorithmus von Dijkstra den kürzesten Pfad und im Folgeschritt entferne ich die nächste Kante, wobei die vorherige entfernte Kante wieder hinzugefügt wird. Der ganze Spaß geht so lange, bis ich am Ende der Matrix angekommen bin.

Ich habe hier mal einen Pseudocode:

#Zeige mir alle Wege an
if degSP > 1 then # Grad vom Startpunkt ist größer als 1
tmp = 0 # tmp-Wert für Graph(i,j)
used = false # Vermerk, ob Kante entfernt wurde
diagonal = 0 # Vermerk, ob aktuelle Position in Diagonale liegt

for i = 0 to n-1 do:
if i != sp then # Nicht in richtiger Zeile?
i = i+1 # ab in die nächste Zeile
end
for j = 0 to n-1 do:
if j == diagonal then # Falls Spalte j in der Diagnale liegt
diagonal = "INFINITY - 1" # Diagonalvermerk aktivieren
else # Ansonsten nicht...
# Verhinderung einer Schleife bzw. Schlinge
Ausgabe Matrix(/*graph*/bin) # zur Kontrolle

/* Wiederherstellung vorheriger entfernter Kante;
* Nur möglich, wenn vorherige entfernte Kante
* wirklich existierte!
*
* Erweiterung: Wenn vorherige Spalte die
* Diagonale ist, muss überprüft
* werden, ob Spalte vor Diagonale
* 0 ist und diese eine Kante hatte
*
* bin(i,j-1) == 0: vorherige Spalte der Binärmatrix
* muss 0 sein
*
* bin(i,j-1) != diagonal: vorherige Spalte darf nicht
* in der Diagonale liegen
*
* used == true: Vermerk, dass eine Kante
* entfernt wurde
*
*/

/* Wenn Spalte j-1, falls existent, 0 ist, überprüfe,
* ob diese in der Diagonale liegt und diese den
* Vermerk gesetzt bekam. Dann ist in dieser Spalte eine
* Kante entfernt worden. Diese wird wieder hinzugefügt
* und der Vermerk zurückgesetzt.
*
* Sonst muss die Spalte j-1 in der Diagonale liegen.
* In diesem Fall muss geprüft werden, ob in der
* Spalte j-2, falls existent, eine 0 steht und dort
* ein Vermerk gesetzt wurde. Dann ist hier eine entfernte
* Kante wieder hinzuzufügen und der Vermerk zurückzusetzen.
*
* Ansonsten ist die Spalte j-1 schon immer 0 gewesen.
* In dem Fall ist j-1 in der Diagonale bzw. wurde
* keine Kante entfernt und Vermerk wurde nie gesetzt.
* Demnach darf keine Kante hinzugefügt werden.
*/
if (bin(i,j-1) == 0) then # Vorherige Spalte 0?
if (bin(i,j-1) != diagonal) and (used == true) then # Vorgerige Spalte keine Diagonale und Vermerk gesetzt?
bin(i,j-1) = 1 # Kante wieder herstellen
graph(i,j-1) = tmp # Wert aus tmp wieder in Matrix speichern
used = false # Vermerk zurücksetzen
else if (bin(i,j-2) == 0) and (used == true) then # Spalte vor Diagonale 0 und Vermerk gesetzt?
bin(i,j-2) = 1 # diese Kante nun wieder herstellen
graph(i,j-2) = tmp # Wert wieder herstellen
used = false # Vermerk zurücksetzen
end
end

/* Entfernen der aktuellen Kante */
if (bin(i,j) == 1) then # Kante vorhanden?
bin(i,j) = 0 # Kante entfernen
tmp = graph(i,j) # Wert sichern
graph(i,j) = INFINITY # "unendlich"
used = true # Vermerk aktivieren
end

/* Es wurde nun in der Theorie eine Kante in der
* Spalte j entfernt und in der vorherigen Spalte
* j-1 eine Kante wieder hinzugefügt, sofern in der
* vorherigen Spalte j-1 der Wert 0 vorhanden war
*/

Berechnung Pfad mit Dijkstra(graph) # Wegfindung des aktuellen Graphen

Ausgabe Pfad(graph) # Ausgabe des Pfades

end
end
end
end
#Ende der Funktion

Nun zu meiner Frage: Da ich schon seit einigen Wochen mich mit dieser Problematik auseinandersetze, aber immer noch nicht den richtigen Zündfunken habe, frage ich nun die Community. Entweder ist etwas oder einiges an meiner Überlegung falsch oder ich habe es noch nicht richtig implementiert.
Könnt ihr dies nachvollziehen, worum es bei der Überlegung und des Pseudocodes, auch wenn das hier bedauerlicherweise nicht besonders schön dargestellt wird, geht oder hat einer von euch da draußen eine oder mehrere Lösung(en) parat?

Also am besten den Pseudocode mal kopieren und in einem beliebigen Editor mittels Tab-Einrückungen näher begutachten ;-)
Ach, bevor ich es vergesse: Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: []hier.


        
Bezug
Wegfindung im Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:48 So 01.12.2013
Autor: reverend

Hallo Parano.Oya, [willkommenmr]

da hast Du im anderen Forum ja schon eine ziemlich umfangreiche Diskussion losgestoßen. Ich fürchte, dass wir Dir zum Ganzen auch nicht mehr helfen können als die Mitglieder dort. Mit Einzelfragen kannst Du aber natürlich gern zurückkommen.

Aufgrund dieser Einschätzung habe ich Deine Frage mal inaktiv gestellt. Ich hoffe, das ist ok.
Außerdem werde ich Deine Anfrage kurz editieren, da der Link nicht funktioniert.

Grüße
reverend

Bezug
        
Bezug
Wegfindung im Graphen: Tipp
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 05:51 Mi 04.12.2013
Autor: Parano.Oya

Heureka! Ich glaub, ich habe die Lösung gefunden! Wenn man nicht daran denkt, dann kommt die Lösung :D

Meine Überlegung war schon richtig, nur gab es EINEN Faktor, den ich nicht richtig begutachtet hatte. Für diejenigen, die (irgendwann) auf das ähnliche oder gleiche "Problem" stoßen sollten, habe ich hier den Tipp, dass der Wert 'diagonal' innerhalb der 2. for-Schleife nicht wirklich als Vergleich herangezogen werden sollte, sondern dass für die Dimension der Matrix eine gleichgroße Markierer-Matrix herangezogen werden sollte, sodass nur in der Koordinate[i][j] es eine Diagonale geben kann. In allen anderen Koordinaten der selben Zeile gibt es dann logischer Weise keine Diagonale.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]