Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Dijkstra Algorithmus für Exzentrizität

Dijkstra Algorithmus für Exzentrizität

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
bafana

bafana aktiv_icon

15:14 Uhr, 17.12.2021

Antworten
Kann man den Dijkstra Algorithmus zur Entwerfung eines Algorithmus in Pseudocode benutzen, wenn ich die Exzentrizität mit Laufzeit O(n+m), der für einen gegebenen Graphen G und Knoten v∈V den Wert ex(v) bestimmen soll?

1:function Dijkstra(Graph, source):
2:for each vertex v in Graph: / Initialization
3:dist[v] := infinity / initial distance from source to vertex v is set to infinite
4:previous[v] := undefined / Previous node in optimal path from source
5:dist[source] :=0/ Distance from source to source
6:Q:= the set of all nodes in Graph / all nodes in the graph are unoptimized - thus are in Q
7:while Q is not empty: / main loop
8:u:= node in Q with smallest dist[ ]
9:remove u from Q
10:for each neighbor v of u:/ where v has not yet been removed from Q.
11:alt := dist[u] + dist_between(u, v)
12:if alt < dist[v] / Relax (u,v)
13:dist[v] := alt
14:previous[v] :=u
15:return previous[ ]

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.