Shortest path tree in linearer Zeit |
| 08.01.2013, 12:04 | MrsWallace | Auf diesen Beitrag antworten » |
| Shortest path tree in linearer Zeit Hallo, ich finde keinen Ansatz für die folgende Aufgabe, vielleicht kann mir einer helfen? Ich soll zeigen, dass man in linearer Zeit einen SPT mit der Wurzel, die mit s bezeichnet wird, berechnen kann. Der zugrundeliegende ungerichtete Graph G hat die Kantengewichte c: E(G) -> {0,1,...,42}. Meine Ideen: Das müsste heißen, dass ich insgesamt 43 Kanten habe. Dijkstras Algorithmus kenne ich schon, bis jetzt hat er mir jedoch nicht weitergeholfen (da keine lineare Laufzeit)... Ich weiß schon, dass ich einzelne kürzeste Wege in linearer Zeit berechnen kann, verstehe aber nicht, wie ich den ganzen Baum ebenfalls in linearer Zeit berechnen kann. Ich danke jetzt schonmal für Eure Hilfe! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
