www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de