Ich habe die drei studiert und meine Schlussfolgerungen von ihnen unten dargelegt. Kann mir jemand sagen, ob ich sie genau genug verstanden habe oder nicht? Vielen Dank.Habe ich Recht bezüglich der Unterschiede zwischen den Algorithmen von Floyd-Warshall, Dijkstra und Bellman-Ford?
Dijkstra-Algorithmus wird nur dann verwendet, wenn Sie eine Hand haben und Sie mögen von einem Knoten zum anderen den kleinsten Weg kennen, aber nicht in Fällen wie this
Floyd-Warshall-Algorithmus verwendet wird, wenn Jeder der Knoten kann eine Quelle sein, dh Sie möchten, dass die kürzeste Entfernung jeden Zielknoten von einem beliebigen Quellknoten erreicht. Dies nicht nur, wenn es negative Zyklen
(dies ist das wichtigste. Ich meine, das ist die, die ich bin wenigstens sicher :)
3.Bellman-Ford benutzt wie Dijkstra, wenn es nur eine Quelle gibt. Dies kann mit negativen Gewichtungen umgehen und seine Arbeit ist die gleiche wie Floyd-Warshall's abgesehen von einer Quelle, richtig?
Wenn Sie einen Blick haben müssen, sind die entsprechenden Algorithmen (mit freundlicher Genehmigung Wikipedia):
Bellman-Ford:
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges: // uv is the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
Dijkstra:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 // from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 if dist[u] = infinity:
14 break ; // all remaining vertices are
15 // inaccessible from source
16
17 remove u from Q ;
18 for each neighbor v of u: // where v has not yet been
19 removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 return dist;
Floyd-Warshall:
1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
2 (infinity if there is none).
3 Also assume that n is the number of vertices and edgeCost(i,i) = 0
4 */
5
6 int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8 from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to
9 edgeCost(i,j).
10 */
11
12 procedure FloydWarshall()
13 for k := 1 to n
14 for i := 1 to n
15 for j := 1 to n
16 path[i][j] = min (path[i][j], path[i][k]+path[k][j]);
Vielleicht ist die Art, wie die Algorithmen in einem Lehrbuch geschrieben werden, es nur für Single-Source verwendet wird aussehen wie Dijkstra macht, aber diese Algorithmen können für mehrere Quellen und mehrere Ziele mit fast keiner Änderung verwendet werden. Bei Dijkstra starten Sie indem Sie Ihren Quellknoten in eine Prioritätswarteschlange mit Abstand = 0 versetzen, wenn Sie mehrere Quellen haben möchten, schieben Sie einfach alle Ihre Quellen mit Distanz = 0 hinein. Alternativ können Sie allen Quellscheitelpunkten einen einzelnen Stützpunkt mit nullwertigen Kanten hinzufügen und diesen Stützpunkt dann als Ihre echte Quelle verwenden. –
Genaues Duplikat von: http://programmers.stackexchange.com/questions/158613/am-i-right-about-the-differences-between-floyd-warshall-dijkstras-and-bellman –