هل أنا على حق بشأن الاختلافات بين خوارزميات فلويد-وارشال وديكسترا وبيلمان-فورد؟

Question

لقد كنت أدرس الثلاثة وأذكر استنتاجاتي منهم أدناه.هل يمكن لأحد أن يخبرني إذا كنت قد فهمتها بدقة كافية أم لا؟شكرًا لك.

1. يتم استخدام خوارزمية Dijkstra فقط عندما يكون لديك مصدر واحد وتريد معرفة أصغر مسار من عقدة إلى أخرى، ولكنها تفشل في حالات مثل هذا

2. يتم استخدام خوارزمية Floyd-Warshall عندما تكون أي من جميع العقد مصدرًا، لذلك تريد أقصر مسافة للوصول إلى أي عقدة وجهة من أي عقدة مصدر.وهذا يفشل فقط عندما تكون هناك دورات سلبية

(وهذا هو الأهم.أعني أن هذا هو الشيء الذي لست متأكدًا منه :)

3. يتم استخدام Bellman-Ford مثل Dijkstra، عندما يكون هناك مصدر واحد فقط.هذا يمكن التعامل مع الأوزان السلبية و عملها هو نفس عمل فلويد-وارشال باستثناء مصدر واحد، أليس كذلك؟

إذا كنت بحاجة إلى إلقاء نظرة، فإن الخوارزميات المقابلة هي (مجاملة ويكيبيديا):

بيلمان فورد:

 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"

ديكسترا:

 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;

فلويد-وارشال:

 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] );

Answer 1

أنت على حق فيما يتعلق بالسؤالين الأولين، وفيما يتعلق بهدف فلويد-وارشال (إيجاد أقصر المسارات بين جميع الأزواج)، ولكن ليس فيما يتعلق بالعلاقة بين بيلمان-فورد وفلويد-وارشال:تستخدم كلتا الخوارزميتين برمجة ديناميكية للعثور على أقصر مسار، لكن FW ليس مثل تشغيل BF من كل عقدة بداية إلى كل عقدة أخرى.

في BF السؤال هو:ما هو أقصر مسار من المصدر إلى الهدف باستخدام خطوات k على الأكثر، ووقت التشغيل هو O(Eالخامس).إذا أردنا تشغيلها على كل عقدة أخرى، فسيكون وقت التشغيل هو O(Eالخامس ^ 2).

في FW السؤال هو:ما هو أقصر مسار من i إلى j إلى k لجميع العقد i,j,k.يؤدي هذا إلى وقت تشغيل O(V^3) - أفضل من BF لكل عقدة بداية (بعامل يصل إلى |V| للرسوم البيانية الكثيفة).

ملاحظة أخرى حول الدورات/الأوزان السلبية:قد يفشل Dijkstra ببساطة في إعطاء النتائج الصحيحة.لن يفشل BF وFW - سيذكران بشكل صحيح أنه لا يوجد حد أدنى لمسار الوزن، نظرًا لأن الوزن السالب غير محدود.

Answer 2

أقصر المسارات بمصدر واحد:

خوارزمية ديكسترا - غير مسموح بالوزن السلبي - O(E+Vlg(V))

خوارزمية بيلمان فورد - الوزن السلبي مسموح به.ولكن في حالة وجود دورة سلبية، سيكتشف بيلمان فورد الدورة -ve - O(VE)

الرسم البياني الحلقي الموجه - كما يوحي الاسم، فهو يعمل فقط مع DAG - O(V+E)

جميع الأزواج أقصر المسارات:

خوارزمية ديكسترا - غير مسموح بالوزن السلبي - O(VE + V^2lg(V))

خوارزمية بيلمان فورد - O(V^2E)

طريقة ضرب سلسلة المصفوفات - التعقيد مماثل لخوارزمية بيلمان فورد

خوارزمية فلويد وارشال - تستخدم طريقة البرمجة الديناميكية - التعقيد هو O(V^3)