Graphentheorie: Beispiel für Kürzeste-Wege-Problem mit negativem Kantengewicht |
21.05.2009, 14:48 | Student_Michael | Auf diesen Beitrag antworten » |
Graphentheorie: Beispiel für Kürzeste-Wege-Problem mit negativem Kantengewicht dies ist mein erster Eintrag in diesem Forum. Ich hoffe ihr könnt mir bei meinem kleinem Problem helfen. Ich schreibe gerade eine Seminararbeit über das Kürzeste-Wege-Problem. Im Moment beschreibe ich den Bellmann-Ford-Algorithmus der auch negative Kantengewichte zulässt. Zu meiner Frage: Ich suche ein einfaches Anwendungsbeispiel aus dem ich einen Graphen mit negativen Kantengewichten ableiten kann. Es sollte ein möglichst einfaches Beispiel sein. Ich würde mich sehr freuen, wenn ich mir bei dieser Sache helfen könntet. Mit freundlichem Gruß Michael |
||
22.05.2009, 22:55 | kaguya_hime | Auf diesen Beitrag antworten » |
RE: Graphentheorie: Beispiel für Kürzeste-Wege-Problem mit negativem Kantengewicht Ein einfaches Anwendungsbeispiel ist eine Spedition, die für eine Fahrt zwischen zwei Zielen die Transportkosten und den Erlös zusammenrechnet Sagen wir mal, sie kann von A nach B lukrative Fracht laden was inklusive Sprit Kosten von -100 Talern verursacht . Auf dem Rückweg von B nach A kann hingegen nur Grind geladen werden und die Kosten belaufen sich auf 20 Taler. |
||
23.05.2009, 10:17 | Student_Michael | Auf diesen Beitrag antworten » |
Danke für dein Beispiel! Dein Beispiel ist so ähnlich wie eine Umrundung auf dem Monopolyfeld. Auf manchen Felder bekommt man Geld, auf manchen muss man welches abgeben. Ich hab auch schon an eine Route durch das Gebirge mit Steigungen und Gefälle gedacht. Gibt es nicht ein noch einfacheres Beispiel. Eines das nahezu jeder kennt und sich sehr einfach beschreiben lässt? |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|