Dijkstra-Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:33 Mo 22.05.2006 | | Autor: | Roemer |
| Aufgabe | | Gegeben sei ein zusammenhängendes Netzwerk, in dem jeder Eckpunkt einen Grad ≤5 besitzt. Zeigen Sie, dass man dann für den Dijkstra-Algorithmus eine erheblich bessere Laufzeit erhält als im allgemeinen Fall. |
Ich weiß zwar wie ein Dijkstra Algorithmus geht, allerdings verstehe ich die Aufgabenstellung nicht genau. Ich weiß nicht, was ich zeigen soll. Kann mir jemand helfen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
könnt gemeint sein, dass halt dann die Laufzeit O(|V|) ist, da nämlich für solche Graphen |E|=O(|V|) gilt ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:29 Mi 24.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
