خوارزمية بلمان فورد و فلويد وارشال و ديكسترا

خوارزمية بلمان-فورد

خوارزمية بِلمان فورد Bellman-Ford هي إحدى خوارزميات إيجاد شجرة المسار الأقصر، وتتميز عن خوارزمية ديكسترا Dijkstra بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة، إلى جانب أنّ خوارزمية بِلمان-فورد أبسط من خوارزمية ديكسترا وهي ملائمة للأنظمة الموزّعة. ولكن ما يعيب هذه الخوارزمية هو أنّ التعقيد الزمني لها هو O(VE)‎ وهو أعلى من التعقيد الزمني لخوارزمية ديكسترا.

خطوات عمل الخوارزمية

يمكن تقسيم الخوارزمية إلى الخطوات التالية:

المدخلات: الرسم البياني والرأس المصدر src.

المخرجات: المسافة الأقصر بين المصدر وجميع الرؤوس في الرسم البياني. إن كانت هناك دورة وزن سالبة negative weight cycle لن تحسب الخوارزمية المسافات الأقصر، بل ستبلّغ عن وجود دورة وزن سالب.

1- الخطوة الأولى هي تهيئة المسافات التي تفصل بين جميع الرؤوس والرأس المصدر لتحمل القيمة ما لانهاية، والمسافة التي تفصل بين المصدر ونفسه لتكون صفرًا. ننشئ المصفوفة dist[]‎ ذات الحجم |V| وتكون جميع القيم فيها هي ما لا نهاية باستثناء العنصر dist[src]‎ الذي سيكون الرأس المصدر.

2- تحسب هذه الخطوة المسافات الأقصر. تُنفّذ الخطوات التالية ‎|V|-1‎ مرة (|V| هو عدد الرؤوس في الرسم البياني المعطى.

a. يُنفّذ ما يلي لكل ضلع u-v:
إن كان dist[v] > dist[u] + weight، نحدّث القيمة dist[v]‎ لتصبح:

dist[v] = dist[u] + weight للضلع uv

3- تبلّغ هذه الخطوة عن وجود دورة وزن سالب في الرسم البياني، وتنفّذ ما يلي لكل ضلع u-v:
إن كانت dist[v] > dist[u] + weight فهذا يعني وجود دورة وزن سالب في الرسم البياني.

تضمن الخطوة الثانية حساب أقصر المسافات إن لم يحتو الرسم البياني على دورة وزن سالب. ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب، وهذا هو الهدف من الخطوة الثالثة.

تحسب الخوارزمية المسارات الأقصر من الأسفل إلى الأعلى، إذ تحسب في البداية المسارات الأقصر والتي تمتلك ضلعًا واحدًا في المسار على الأكثر، ثم تحسب الخوارزمية المسارات الأقصر التي تمتلك ضلعين على الأكثر، وهكذا دواليك. وبعد الدورة i للحلقة التكرارية الخارجية، تحسب الخوارزمية المسارات الأقصر التي تمتلك i ضلع على الأكثر. إن أقصى عدد من الأضلاع التي يمكن أن تكون موجودة في أي مسار بسيط هو ‎|V|-1 ضلع، ولهذا السبب تعمل الحلقة الخارجية ‎|v|-1‎ مرة.

هذا يعني أنّه لو فرضنا عدم وجود دورة وزن سالبة في الرسم البياني، فإن حسبنا المسارات الأقصر التي تمتلك i من الأضلاع على الأكثر، فإنّ المرور على جميع الأضلاع يعني ضمان إعطاء مسار أقصر يمتلك على الأكثر i+1 من الأضلاع.

يمكن توضيح خطوات الخوارزمية باستخدام المخطط التالي:

ليكن الرأس المصدر صفرًا، سنهيّئ جميع المسافات لتكون ما لا نهاية، باستثناء مسافة المصدر. لما كان عدد الرؤوس الكلي في الرسم البياني هو 5، فإنّ جميع الأضلاع ستعالج 4 مرّات.

لنفترض أنّ جميع الأضلاع ستعالج بالترتيب التالي: ‎(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D)‎. سنحصل على المسافات التالية عند معالجة جميع الأضلاع للمرة الأولى.

يعرض الصف الأول في الصورة المسافات الابتدائية، ويعرض الصف الثاني المسافات الناتجة عن معالجة الأضلاع (B, E) و (D,B) و (B,D) و (A,B)، ويعرض الصف الثالث المسافات عند معالجة الضلع (A,C)، ويعرض الصف الرابع المسافات عند معالجة الأضلاع (D,C) و (B,C) و (E,D).

تضمن الدورة الأولى إعطاء جميع المسارات الأقصر والتي يكون طولها ضلعًا واحدًا على الأكثر.

تؤدي معالجة جميع الأضلاع للمرة الثانية إلى الحصول على المسافات التالية (يعرض الصف الأخير القيم النهائية).

تضمن الدورة الثانية إعطاء جميع المسارات الأقصر والتي يكون طولها ضلعين على الأكثر. ثم تعالج الخوارزمية جميع الأضلاع مرتين إضافيتين، وتُقلّص المسافات بعد الدورة الثانية؛ لذا لا تحدّث الدورتان الثالثة والرابعة قيم المسافات.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية بِلمان-فورد في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 

		  // تمثيل ضلع موزون في الرسم البياني
		  struct Edge 
		  { 
		  int src, dest, weight; 
		  }; 

		  // تمثيل رسم بياني متصل وموجّه وموزون
		  struct Graph 
		  { 
		  // V -> عدد الرؤوس
		  // E -> عدد الأضلاع	
		  int V, E; 

		  // يُمثّل الرسم البياني كمصفوفة من الأضلاع	
		  struct Edge* edge; 
		  }; 

		  // إنشاء رسم بياني يمتلك الرؤوس والأضلاع المعطاة
		  struct Graph* createGraph(int V, int E) 
		  { 
		  struct Graph* graph = new Graph; 
		  graph->V = V; 
		  graph->E = E; 
		  graph->edge = new Edge[E]; 
		  return graph; 
		  } 

		  // دالة مساعدة لطباعة الحلّ
		  void printArr(int dist[], int n) 
		  { 
		  printf("Vertex Distance from Source\n"); 
		  for (int i = 0; i < n; ++i) 
		  printf("%d \t\t %d\n", i, dist[i]); 
		  } 

		  // الدالة الرئيسية التي تستخدم للعثور على المسافات الأقصر من المصدر
		  // إلى جميع الرؤوس باستخدام خوارزمية بِلمان-فورد. تكشف الدالة كذلك
		  // عن دورة الوزن السالب في الرسم البياني
		  void BellmanFord(struct Graph* graph, int src) 
		  { 
		  int V = graph->V; 
		  int E = graph->E; 
		  int dist[V]; 

		  // الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
		  // وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية	
		  for (int i = 0; i < V; i++) 
		  dist[i] = INT_MAX; 
		  dist[src] = 0; 

		  // الخطوة الثانية: إطلاق جميع الأضلاع.
		  // يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
		  // |V| -1 ضلعًا
		  for (int i = 1; i <= V-1; i++) 
		  { 
		  for (int j = 0; j < E; j++) 
		  { 
		  int u = graph->edge[j].src; 
		  int v = graph->edge[j].dest; 
		  int weight = graph->edge[j].weight; 
		  if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
		  dist[v] = dist[u] + weight; 
		  } 
		  } 

		  // تضمن الخطوة الثانية حساب أقصر المسافات
		  // إن لم يحتو الرسم البياني على دورة وزن سالب.
		  // ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
		  // لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب 
		  for (int i = 0; i < E; i++) 
		  { 
		  int u = graph->edge[i].src; 
		  int v = graph->edge[i].dest; 
		  int weight = graph->edge[i].weight; 
		  if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
		  printf("Graph contains negative weight cycle"); 
		  } 

		  printArr(dist, V); 

		  return; 
		  } 

		  // اختبار الدوال السابقة
		  int main() 
		  { 
		  /* إنشاء الرسم البياني في الشكل أعلاه */
		  int V = 5; // عدد الرؤوس في الرسم البياني
		  int E = 8; // عدد الأضلاع في الرسم البياني
		  struct Graph* graph = createGraph(V, E); 

		  // إضافة الضلع 1-0
		  graph->edge[0].src = 0; 
		  graph->edge[0].dest = 1; 
		  graph->edge[0].weight = -1; 

		  // إضافة الضلع 2-0
		  graph->edge[1].src = 0; 
		  graph->edge[1].dest = 2; 
		  graph->edge[1].weight = 4; 

		  // إضافة الضلع 2-1
		  graph->edge[2].src = 1; 
		  graph->edge[2].dest = 2; 
		  graph->edge[2].weight = 3; 

		  // إضافة الضلع 3-1
		  graph->edge[3].src = 1; 
		  graph->edge[3].dest = 3; 
		  graph->edge[3].weight = 2; 

		  // إضافة الضلع 4-1
		  graph->edge[4].src = 1; 
		  graph->edge[4].dest = 4; 
		  graph->edge[4].weight = 2; 

		  // إضافة الضلع 2-3
		  graph->edge[5].src = 3; 
		  graph->edge[5].dest = 2; 
		  graph->edge[5].weight = 5; 

		  // إضافة الضلع 1-3
		  graph->edge[6].src = 3; 
		  graph->edge[6].dest = 1; 
		  graph->edge[6].weight = 1; 

		  // إضافة الضلع 3-4
		  graph->edge[7].src = 4; 
		  graph->edge[7].dest = 3; 
		  graph->edge[7].weight = -3; 

		  BellmanFord(graph, 0); 

		  return 0; 
		  }
		

• بايثون:

# يستخدم هذا الصنف لتمثيل الرسم البياني
		  class Graph: 

		  def __init__(self,vertices): 
		  self.V= vertices # عدد الرؤوس
		  self.graph = [] # قاموس افتراضي لتخزين الرسم البياني

		  # تضيف الدالة ضلعًا إلى الرسم البياني
		  def addEdge(self,u,v,w): 
		  self.graph.append([u, v, w]) 

		  # دالة مساعدة لطباعة الحل
		  def printArr(self, dist): 
		  print("Vertex Distance from Source") 
		  for i in range(self.V): 
		  print("%d \t\t %d" % (i, dist[i])) 

		  # الدالة الرئيسية والتي تعثر على المسافات الأقصر التي تفصل
		  # المصدر عن جميع الرؤوس باستخدام خوارزمية بِلمان-فورد.
		  # تكشف الدالة كذلك عن دورة الوزن السالب.

		  def BellmanFord(self, src): 

		  # الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
		  # وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية
		  dist = [float("Inf")] * self.V 
		  dist[src] = 0

		  # الخطوة الثانية: إطلاق جميع الأضلاع.
		  # يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
		  # |V| -1 ضلعًا
		  for i in range(self.V - 1): 
		  # تحديث قيمة المسافة وموقع الأب للرؤوس المجاورة
		  # للرأس المنتخب. سنأخذ بنظر الاعتبار الرؤوس التي لا تزال موجودة في الرتل فقط.		
		  for u, v, w in self.graph: 
		  if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
		  dist[v] = dist[u] + w 

		  # تضمن الخطوة الثانية حساب أقصر المسافات
		  # إن لم يحتو الرسم البياني على دورة وزن سالب.
		  # ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
		  # لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب		

		  for u, v, w in self.graph: 
		  if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
		  print "Graph contains negative weight cycle"
		  return

		  # طباعة قيم المسافات كلها
		  self.printArr(dist) 

		  g = Graph(5) 
		  g.addEdge(0, 1, -1) 
		  g.addEdge(0, 2, 4) 
		  g.addEdge(1, 2, 3) 
		  g.addEdge(1, 3, 2) 
		  g.addEdge(1, 4, 2) 
		  g.addEdge(3, 2, 5) 
		  g.addEdge(3, 1, 1) 
		  g.addEdge(4, 3, -3) 

		  # طباعة الحل
		  g.BellmanFord(0)
		

• جافا:

// A Java program for Bellman-Ford's single source shortest path 
		  // algorithm. 
		  import java.util.*; 
		  import java.lang.*; 
		  import java.io.*; 

		  // تمثيل رسم بياني متصل وموجّه وموزون 
		  class Graph 
		  { 
		  // يستخدم هذا الصنف لتمثيل ضلع موزون في الرسم البياني 
		  class Edge { 
		  int src, dest, weight; 
		  Edge() { 
		  src = dest = weight = 0; 
		  } 
		  }; 

		  int V, E; 
		  Edge edge[]; 

		  // إنشاء رسم بياني يمتلك الرؤوس والأضلاع المعطاة 
		  Graph(int v, int e) 
		  { 
		  V = v; 
		  E = e; 
		  edge = new Edge[e]; 
		  for (int i=0; i<e; ++i) 
		  edge[i] = new Edge(); 
		  } 

		  // الدالة الرئيسية التي تستخدم للعثور على المسافات الأقصر من المصدر
		  // إلى جميع الرؤوس باستخدام خوارزمية بِلمان-فورد. تكشف الدالة كذلك
		  // عن دورة الوزن السالب في الرسم البياني 
		  void BellmanFord(Graph graph,int src) 
		  { 
		  int V = graph.V, E = graph.E; 
		  int dist[] = new int[V]; 

		  // الخطوة الأولى هي تهيئة المسافات التي تفصل بين المصدر
		  // وجميع الرؤوس في الرسم البياني لتكون ما لا نهاية	
		  for (int i=0; i<V; ++i) 
		  dist[i] = Integer.MAX_VALUE; 
		  dist[src] = 0; 

		  // الخطوة الثانية: إطلاق جميع الأضلاع.
		  // يمكن للمسار الأقصر البسيط من المصدر إلى أي عقدة أن يمتلك
		  // |V| -1 ضلعًا 
		  for (int i=1; i<V; ++i) 
		  { 
		  for (int j=0; j<E; ++j) 
		  { 
		  int u = graph.edge[j].src; 
		  int v = graph.edge[j].dest; 
		  int weight = graph.edge[j].weight; 
		  if (dist[u]!=Integer.MAX_VALUE && 
		  dist[u]+weight<dist[v]) 
		  dist[v]=dist[u]+weight; 
		  } 
		  } 

		  // تضمن الخطوة الثانية حساب أقصر المسافات
		  // إن لم يحتو الرسم البياني على دورة وزن سالب.
		  // ولكن إن مررنا على جميع الأضلاع مرة أخرى وحصلنا على مسار أقصر
		  // لأي رأس من الرؤوس في الرسم البياني فهذا يعني وجود دورة وزن سالب 
		  for (int j=0; j<E; ++j) 
		  { 
		  int u = graph.edge[j].src; 
		  int v = graph.edge[j].dest; 
		  int weight = graph.edge[j].weight; 
		  if (dist[u] != Integer.MAX_VALUE && 
		  dist[u]+weight < dist[v]) 
		  System.out.println("Graph contains negative weight cycle"); 
		  } 
		  printArr(dist, V); 
		  } 

		  // دالة مساعدة لطباعة الحل 
		  void printArr(int dist[], int V) 
		  { 
		  System.out.println("Vertex Distance from Source"); 
		  for (int i=0; i<V; ++i) 
		  System.out.println(i+"\t\t"+dist[i]); 
		  } 

		  // اختبار الدوال السابقة
		  public static void main(String[] args) 
		  { 
		  int V = 5; // عدد الرؤوس في الرسم البياني
		  int E = 8; // عدد الأضلاع في الرسم البياني

		  Graph graph = new Graph(V, E); 

		  // إضافة الضلع 1-0 
		  graph.edge[0].src = 0; 
		  graph.edge[0].dest = 1; 
		  graph.edge[0].weight = -1; 

		  // إضافة الضلع 2-0 
		  graph.edge[1].src = 0; 
		  graph.edge[1].dest = 2; 
		  graph.edge[1].weight = 4; 

		  // إضافة الضلع 2-1 
		  graph.edge[2].src = 1; 
		  graph.edge[2].dest = 2; 
		  graph.edge[2].weight = 3; 

		  // إضافة الضلع 3-1 
		  graph.edge[3].src = 1; 
		  graph.edge[3].dest = 3; 
		  graph.edge[3].weight = 2; 

		  // إضافة الضلع 4-1 
		  graph.edge[4].src = 1; 
		  graph.edge[4].dest = 4; 
		  graph.edge[4].weight = 2; 

		  // إضافة الضلع 2-3 
		  graph.edge[5].src = 3; 
		  graph.edge[5].dest = 2; 
		  graph.edge[5].weight = 5; 

		  // إضافة الضلع 1-3 
		  graph.edge[6].src = 3; 
		  graph.edge[6].dest = 1; 
		  graph.edge[6].weight = 1; 

		  // إضافة الضلع 3-4 
		  graph.edge[7].src = 4; 
		  graph.edge[7].dest = 3; 
		  graph.edge[7].weight = -3; 

		  graph.BellmanFord(graph, 0); 
		  } 
		  }
		

تعطي الشيفرات السابقة المخرجات التالية:

Vertex   Distance from Source
		  0                0
		  1                -1
		  2                2
		  3                -2
		  4                1
		

ملاحظات:

1. الأضلاع السالبة موجودة في الكثير من تطبيقات الرسوم البيانية، فعلى سبيل المثال، عوضًا عن دفع ثمن معين من أجل مسار ما، يمكن أن نستفيد من السير على ذلك المسار.
2. تؤدي خوارزمية بِلمان-فورد أداءً أفضل (أفضل من خوارزمية ديكسترا) في الأنظمة الموزّعة distributed systems. وعلى العكس من خوارزمية ديكسترا والتي تحتاج إلى العثور على القيمة الصغرى لجميع الرؤوس، فإنّ خوارزمية بِلمان-فورد تمرّ على الأضلاع واحدًا تلو الآخر.

خوارزمية فلويد وارشال

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

المدخلات:
		  graph[][] = { {0,   5,  INF, 10},
		  {INF,  0,  3,  INF},
		  {INF, INF, 0,   1},
		  {INF, INF, INF, 0} }

		  تمثل المدخلات الرسم البياني التالي:

		  10
		  (0)------->(3)
		  |         /|\
		  5 |          |
		  |          | 1
		  \|/         |
		  (1)------->(2)
		  3
		

لاحظ أنّ القيمة graph[i][j]‎ هي 0 إن كانت i تساوي j، وأنّ قيمة graph[i][j]‎ تساوي INF (ما لا نهاية) إن لم يكن هناك ضلع يربط بين الرأسين i و j.

المخرجات:
		  Shortest distance matrix
		  0      5      8      9
		  INF      0      3      4
		  INF    INF      0      1
		  INF    INF    INF      0
		

خطوات الخوارزمية

تبدأ الخوارزمية بتهيئة مصفوفة الحل solution matrix التي تكون مشابهة لمصفوفة الرسم البياني المدخل، ثم تحدّث مصفوفة الحل وذلك باعتبار جميع الرؤوس كرأس وسطي. تنتقي الخوارزمية جميع الرؤوس واحدًا تلو الآخر وتحدث جميع قيم المسارات الأقصر التي تتضمن الرأس المنتخب كرأس وسطي في المسار الأقصر.

عند انتخاب الرأس ذي الرقم k كرأس وسطي، فإنّنا قد عددنا الرؤوس ‎{0, 1, 2, ..k-1}‎ كرؤوس وسطية، ولكل زوج (i, j) لرؤوس المصدر والوجهة على التوالي هناك احتمالان:

1. أن لا يكون k رأسًا وسطيًا في المسار الأقصر الذي يفصل بين i و j؛ لذا نبقي على قيمة dist[i][j]‎ كما هي.
2. أن يكون k رأسًا وسطيًا في المسار الأقصر الذي يفصل بين i و j؛ لذا نحدث قيمة dist[i][j]‎ لتصبح dist[i][k] + disk[k][j]‎ إذا كانت ‎dist[i][j] > dist[i][k] + dist[k][j]‎.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
		  using namespace std; 

		  // عدد الرؤوس في الرسم البياني
		  #define V 4 

		  /* تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.
		  ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض */
		  #define INF 99999 

		  // تطبع الدالة مصفوفة الحل
		  void printSolution(int dist[][V]); 

		  void floydWarshall (int graph[][V]) 
		  { 
		  /* ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي
		  	على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني */
		  int dist[V][V], i, j, k; 


		  /* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
		  	أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
		  	تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
		  	عدم وجود رأس وسطي */
		  for (i = 0; i < V; i++) 
		  for (j = 0; j < V; j++) 
		  dist[i][j] = graph[i][j]; 

		  /* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
		  	الرؤوس الوسية.
		  	---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
		  	بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
		  	{0, 1, 2, .. k-1}
		  	كرؤوس وسطية.
		  	---> بعد انتهاء عمل الحلقة التكرارية
		  	k يضاف الرأس 
		  	إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
		  	{0, 1, 2, .. k}
		  	*/

		  for (k = 0; k < V; k++) 
		  { 
		  // اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر
		  for (i = 0; i < V; i++) 
		  { 
		  // اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة
		  for (j = 0; j < V; j++) 
		  { 
		  // إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر
		  // بين متغير الحلقة الثانية والثالثة فسنحدث قيمة 
		  // dist[i][j]
		  if (dist[i][k] + dist[k][j] < dist[i][j]) 
		  dist[i][j] = dist[i][k] + dist[k][j]; 
		  } 
		  } 
		  } 

		  // طباعة مصفوفة المسافة الأقصر
		  printSolution(dist); 
		  } 

		  /* دالة مساعدة لطباعة الحل */
		  void printSolution(int dist[][V]) 
		  { 
		  cout<<"The following matrix shows the shortest distances"
		  " between every pair of vertices \n"; 
		  for (int i = 0; i < V; i++) 
		  { 
		  for (int j = 0; j < V; j++) 
		  { 
		  if (dist[i][j] == INF) 
		  cout<<"INF"<<" "; 
		  else
		  cout<<dist[i][j]<<" "; 
		  } 
		  cout<<endl; 
		  } 
		  } 

		  // اختبار الدوال السابقة
		  int main() 
		  { 
		  /* إنشاء الرسم البياني الموزون التالي:
		  			10 
		  	(0)------->(3) 
		  		| /|\ 
		  	5 | | 
		  		| | 1 
		  	\|/ | 
		  	(1)------->(2) 
		  			3 */
		  int graph[V][V] = { {0, 5, INF, 10}, 
		  {INF, 0, 3, INF}, 
		  {INF, INF, 0, 1}, 
		  {INF, INF, INF, 0} 
		  }; 

		  // طباعة الحل
		  floydWarshall(graph); 
		  return 0; 
		  }
		

• بايثون:

# عدد الرؤوس في الرسم البياني
		  V = 4

		  # تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.
		  # ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض
		  INF = 99999

		  def floydWarshall(graph): 

		  # ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي
		  # على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني
		  # تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
		  # أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
		  # تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
		  # عدم وجود رأس وسطي

		  dist = map(lambda i : map(lambda j : j , i) , graph) 

		  # إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
		  الرؤوس الوسية.
		  # ---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
		  # بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
		  # {0, 1, 2, .. k-1}
		  # كرؤوس وسطية.
		  # ---> بعد انتهاء عمل الحلقة التكرارية
		  # k يضاف الرأس 
		  # إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
		  # {0, 1, 2, .. k}

		  for k in range(V): 

		  # اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر 
		  for i in range(V): 

		  # اختيار جميع الرؤوس التي ستكون وجهة 
		  # للمصدر المنتخب في الخطوة السابقة 
		  for j in range(V): 

		  # إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر 
		  # بين متغير الحلقة الثانية والثالثة فسنحدث قيمة
		  # dist[i][j]
		  dist[i][j] = min(dist[i][j] , 
		  dist[i][k]+ dist[k][j] 
		  ) 
		  printSolution(dist) 


		  # دالة مساعدة لطباعة الحل
		  def printSolution(dist): 
		  print "Following matrix shows the shortest distances\ 
		  between every pair of vertices" 
		  for i in range(V): 
		  for j in range(V): 
		  if(dist[i][j] == INF): 
		  print "%7s" %("INF"), 
		  else: 
		  print "%7d\t" %(dist[i][j]), 
		  if j == V-1: 
		  print "" 



		  # اختبار الدوال السابقة
		  # إنشاء الرسم البياني الموزون التالي
		  """ 
		  			10 
		  	(0)------->(3) 
		  		|		 /|\ 
		  	5 |		 | 
		  		|		 | 1 
		  	\|/		 | 
		  	(1)------->(2) 
		  			3		 """
		  graph = [[0,5,INF,10], 
		  [INF,0,3,INF], 
		  [INF, INF, 0, 1], 
		  [INF, INF, INF, 0] 
		  ] 
		  # طباعة الحل
		  floydWarshall(graph);
		

• جافا:

import java.util.*; 
		  import java.lang.*; 
		  import java.io.*; 


		  class AllPairShortestPath 
		  { 
		  final static int INF = 99999, V = 4; 

		  void floydWarshall(int graph[][]) 
		  { 
		  int dist[][] = new int[V][V]; 
		  int i, j, k; 

		  /* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.
		  	أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر
		  	تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار
		  	عدم وجود رأس وسطي */
		  for (i = 0; i < V; i++) 
		  for (j = 0; j < V; j++) 
		  dist[i][j] = graph[i][j]; 

		  /* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة
		  	الرؤوس الوسية.
		  	---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني
		  	بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة
		  	{0, 1, 2, .. k-1}
		  	كرؤوس وسطية.
		  	---> بعد انتهاء عمل الحلقة التكرارية
		  	k يضاف الرأس 
		  	إلى مجموعة الرؤوس الوسطية وتصبح المجموعة
		  	{0, 1, 2, .. k}
		  	*/
		  for (k = 0; k < V; k++) 
		  { 
		  // اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر 
		  for (i = 0; i < V; i++) 
		  { 
		  // اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة 
		  for (j = 0; j < V; j++) 
		  { 
		  // إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر
		  // بين متغير الحلقة الثانية والثالثة فسنحدث قيمة 
		  // dist[i][j]
		  if (dist[i][k] + dist[k][j] < dist[i][j]) 
		  dist[i][j] = dist[i][k] + dist[k][j]; 
		  } 
		  } 
		  } 

		  // طباعة مصفوفة المسافة الأقصر 
		  printSolution(dist); 
		  } 

		  void printSolution(int dist[][]) 
		  { 
		  System.out.println("The following matrix shows the shortest "+ 
		  "distances between every pair of vertices"); 
		  for (int i=0; i<V; ++i) 
		  { 
		  for (int j=0; j<V; ++j) 
		  { 
		  if (dist[i][j]==INF) 
		  System.out.print("INF "); 
		  else
		  System.out.print(dist[i][j]+" "); 
		  } 
		  System.out.println(); 
		  } 
		  } 

		  // اختبار الدوال السابقة
		  public static void main (String[] args) 
		  { 
		  /* إنشاء الرسم البياني الموزون التالي: 
		  		10 
		  		(0)------->(3) 
		  		|		 /|\ 
		  		5 |		 | 
		  		|		 | 1 
		  		\|/		 | 
		  		(1)------->(2) 
		  		3		 */
		  int graph[][] = { {0, 5, INF, 10}, 
		  {INF, 0, 3, INF}, 
		  {INF, INF, 0, 1}, 
		  {INF, INF, INF, 0} 
		  }; 
		  AllPairShortestPath a = new AllPairShortestPath(); 

		  // طباعة الحل
		  a.floydWarshall(graph); 
		  } 
		  }
		

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(V3)‎.

يطبع البرنامج أعلاه المسافات الأقصر فقط، ويمكن تعديل الحل ليطبع المسارات الأقصر أيضًا، وذلك بتخزين المعلومات السابقة في مصفوفة ثنائية الأبعاد.

كذلك استخدام القيمة INT_MAX من الترويسة limits.h عوضًا عن القيمة INF وذلك لضمان أنّنا نتعامل مع أكبر قيمة ممكنة، وعند القيام بذلك يجب تعديل عبارة الشرطية في البرنامج أعلاه لتجنب حدوث فيضان حسابي arithmetic overflow.

مصادر

خوارزمية ديكسترا

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

تشبه خوارزمية ديكسترا في عملها إلى حدٍّ كبير خوارزمية برم Prim لإيجاد الشجرة الممتدة الصغرى.

خطوات عمل الخوارزمية

يقسم سير عمل خوارزمية ديكسترا إلى الخطوات التالية:

1. إنشاء مجموعة (ليكن اسمها sptSet) لمتابعة الرؤوس الموجودة في شجرة المسار الأقصر، أي الرؤوس التي قد تمّ حساب مسافتها الصغرى من المصدر. وتكون هذه المجموعة فارغة في البداية.
2. إسناد قيمة للمسافة إلى جميع الرؤوس في الرسم البياني المدخل، ثم تهيئة جميع قيم المسافات لتكون ما لا نهاية INFINITE وإسناد القيمة 0 للرأس المصدر لكي يكون أول رأس تختاره الخوارزمية.
3. إنشاء حلقة تكرارية شرطها عدم وجود جميع الرؤوس في مجموعة sptSet وتؤدي هذه الحلقة الخطوات التالية:
   1. اختيار أحد الرؤوس u من الرسم البياني بشرط أن لا يكون موجودًا في المجموعة sptSet ويمتلك قيمة للمسافة الصغرى.
   2. إضافة u إلى المجموعة sptSet.
   3. تحديث قيمة المسافة لجميع الرؤوس المجاورة للرأس u، وللقيام بذلك نمرّ على جميع الرؤوس المجاورة، ولكل رأس مجاور v، إذا كان مجموعة قيمة المسافة للرأس u (من المصدر) ووزن الضلع u-v أقل من قيمة مسافة الرأس v، فسنحدث حينئذٍ قيمة المسافة للرأس v.

يمكن استخدام الشكل التالي لتوضيح خطوات خوارزمية ديكسترا:

تكون المجموعة sptSet فارغة في البداية، وتكون قيم المسافات المسندة إلى الرؤوس في الرسم البياني هي ‎{0, INF, INF, INF, INF, INF, INF, INF}‎ (ترمز INF إلى ما لا نهاية). والآن نختار الرؤاس الذي يمتلك أصغر قيمة للمسافة، وهو الرأس 0، ونضيفه إلى المجموعة sptSet؛ وبهذا تصبح المجموعة {0}.

بعد إضافة الرأس 0 إلى المجموعة sptSet نجري تحديثًا لقيم المسافة للرؤوس المجاورة له، وهما الرأسان 1 و 7، والذان ستحدّث قيمة المسافة لهما إلى 4 و 8. يعرض الشكل التالي الرؤوس التي تمتلك قيم مسافة محددة فقط، والرؤوس الموجودة في شجرة المسار الأقصر SPT ملوّنة باللون الأحمر.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 1 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 1؛ وبهذا تحدّث قيمة المسافة للرأس 2 إلى القيمة 12.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 7 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1, 7}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 7؛ وبهذا تحدّث قيمة المسافة للرأسين 6 و 8 إلى القيمتين 15 و 9 على التوالي.

الخطوة التالية هي اختيار الرأس الذي يمتلك أقل قيمة للمسافة بشرط أن لا يكون موجودًا في شجرة المسار الأقصر (غير موجود في المجموعة sptSet)، وبهذا يتم اختيار الرأس 6 ويضاف إلى المجموعة sptSet، وبذلك تصبح هذه المجموعة ‎{0, 1, 7, 6}‎، ثم نحدّث قيم المسافة للرؤوس المجاورة للرأس 6؛ وبهذا تحدّث قيمة المسافة للرأسين 5 و 8.

تُكرَّر الخطوات السابقة إلى أن يتحقّق شرط وجود جميع الرؤوس في المجموعة sptSet، وحينها نحصل على شجرة المسار الأقصر.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية ديكسترا في عدد من لغات البرمجة.

تستخدم الأمثلة التالية المصفوفة المنطقية sptSet[]‎ لتمثيل مجموعة الرؤوس المضافة إلى شجرة المسار الأقصر. إن كانت القيمة sptSet[v]‎ قيمة صحيحة فإنّ الرأس v مضاف إلى شجرة المسار الأقصر، وإلا فلا. كذلك تستخدم المصفوفة dist[]‎ لتخزين قيم المسافات الأقصر لجميع الرؤوس في الرسم البياني.

• C++‎:

#include <stdio.h> 
#include <limits.h> 

// عدد الرؤوس في الرسم البياني
#define V 9 

// دالة مساعدة عملها العثور على الرأس الذي يمتلك أصغر قيمة للمسافة
// في مجموعة الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر


int minDistance(int dist[], bool sptSet[]) 
{ 
// تهيئة القيمة الصغرى
int min = INT_MAX, min_index; 

for (int v = 0; v < V; v++) 
	if (sptSet[v] == false && dist[v] <= min) 
		min = dist[v], min_index = v; 

return min_index; 
} 

// دالة مساعدة لطباعة مصفوفة المسافات
int printSolution(int dist[], int n) 
{ 
printf("Vertex Distance from Source\n"); 
for (int i = 0; i < V; i++) 
	printf("%d tt %d\n", i, dist[i]); 
} 


// الدالة التي تنفذ خوارزمية ديكسترا لإيجاد المسار الأقصر من مصدر واحد
// في الرسم البياني المعطى والممثّل بواسطة مصفوفة المجاورة

void dijkstra(int graph[V][V], int src) 
{ 
	// مصفوفة المخرجات.
	// يمثل العنصر
	// dist[i]
	// i المسار الأقصر من المصدر إلى
	int dist[V];
	
	// ستكون القيمة
	// sptSet[i] 
	// i إن كان الرأس
	// موجودًا في 	
	// sptSet[i] will be true if vertex i is included in shortest 
	// path tree or shortest distance from src to i is finalized 
	bool sptSet[V];
	// Initialize all distances as INFINITE and stpSet[] as false 
	for (int i = 0; i < V; i++) 
		dist[i] = INT_MAX, sptSet[i] = false; 
	
	// تكون المسافة التي تفصل الرأس المصدر عن نفسه صفرًا دائمًا
	dist[src] = 0; 

	// إيجاد المسار الأقصر لجميع الرؤوس
	for (int count = 0; count < V-1; count++) 
	{ 
	
	// اختيار الرأس ذي المسافة الأقصر من مجموعة الرؤوس التي لم تُعالج بعد.
	// في الدورة الأولى تكون
	// u == src
	int u = minDistance(dist, sptSet); 
	
	// تعليم الرأس المنتخب على أنّه معالج
	// Mark the picked vertex as processed 
	sptSet[u] = true; 

	// تحديث قيمة المسافة للرؤوس المجاورة للرأس المنتخب	
	for (int v = 0; v < V; v++) 

		// Update dist[v] only if is not in sptSet, there is an edge from 
		// u to v, and total weight of path from src to v through u is 
		// smaller than current value of dist[v] 
		if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
									&& dist[u]+graph[u][v] < dist[v]) 
			dist[v] = dist[u] + graph[u][v]; 
	} 

	// طباعة مصفوفة المسافات التي تم إنشاؤها
	printSolution(dist, V); 
} 

// اختبار الدوال السابقة 
int main() 
{ 
/* إنشاء الرسم البياني الوارد في المثال أعلاه */
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
					{4, 0, 8, 0, 0, 0, 0, 11, 0}, 
					{0, 8, 0, 7, 0, 4, 0, 0, 2}, 
					{0, 0, 7, 0, 9, 14, 0, 0, 0}, 
					{0, 0, 0, 9, 0, 10, 0, 0, 0}, 
					{0, 0, 4, 14, 10, 0, 2, 0, 0}, 
					{0, 0, 0, 0, 0, 2, 0, 1, 6}, 
					{8, 11, 0, 0, 0, 0, 1, 0, 7}, 
					{0, 0, 2, 0, 0, 0, 6, 7, 0} 
					}; 

	dijkstra(graph, 0); 

	return 0; 
}

• بايثون:

import sys 

class Graph(): 

	def __init__(self, vertices): 
		self.V = vertices 
		self.graph = [[0 for column in range(vertices)] 
					for row in range(vertices)] 
	
	def printSolution(self, dist): 
		print "Vertex tDistance from Source"
		for node in range(self.V): 
			print node,"t",dist[node] 
	
	# دالة مساعدة للعثور على الرأس
    # ذي قيمة المسافة الأقصر، من مجموعة الرؤوس
    # التي لم تضف بعد إلى شجرة المسار
	def minDistance(self, dist, sptSet): 
	
		# تهيئة المسافة الأقصر من العقدة التالية
		min = sys.maxsize
	
		# البحث عن أقرب رأس غير موجود في شجرة المسار الأقصر
		for v in range(self.V): 
			if dist[v] < min and sptSet[v] == False: 
				min = dist[v] 
				min_index = v 
	
		return min_index 
	
	# دالة لتنفيذ خوارزمية ديكسترا أحادية المصدر
    # لإيجاد المسار الأقصر لرسم بياني ممثل
    # باستخدام مصفوفة المجاورة
	def dijkstra(self, src): 
	
		dist = [sys.maxsize] * self.V 
		dist[src] = 0
		sptSet = [False] * self.V 
	
		for cout in range(self.V): 
			
            # اختيار المسافة الأقصر من مجموعة
            # الرؤوس التي لم تعالج بعد
            # في الدورة الأولى تكون
            # u == src
			u = self.minDistance(dist, sptSet) 
	
			# وضع الرأس ذي المسافة الأقصر في شجرة المسار الأقصر	
			sptSet[u] = True
	
			# تحديث قيمة المسافة للرؤوس المجاورة
        	# للرأس المنتخب بشرط أن تكون المسافة الحالية
            # أكبر من المسافة الجديدة وأن الرأس
            # غير موجود في شجرة المسار الأقصر
			for v in range(self.V): 
				if self.graph[u][v] > 0 and sptSet[v] == False and
				dist[v] > dist[u] + self.graph[u][v]: 
						dist[v] = dist[u] + self.graph[u][v] 
	
		self.printSolution(dist) 

# اختبار الدوال السابقة
g = Graph(9) 
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
		[4, 0, 8, 0, 0, 0, 0, 11, 0], 
		[0, 8, 0, 7, 0, 4, 0, 0, 2], 
		[0, 0, 7, 0, 9, 14, 0, 0, 0], 
		[0, 0, 0, 9, 0, 10, 0, 0, 0], 
		[0, 0, 4, 14, 10, 0, 2, 0, 0], 
		[0, 0, 0, 0, 0, 2, 0, 1, 6], 
		[8, 11, 0, 0, 0, 0, 1, 0, 7], 
		[0, 0, 2, 0, 0, 0, 6, 7, 0] 
		]; 

g.dijkstra(0);

• جافا:

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class ShortestPath 
{ 
	// دالة مساعدة للعثور على الرأس الذي يمتلك أقل قيمة للمسافة
    // في مجموعة الرؤوس التي لم تضف بعد إلى شجرة المسار الأقصر
	static final int V=9; 
	int minDistance(int dist[], Boolean sptSet[]) 
	{ 
		// تهيئة القيمة الدنيا 
		int min = Integer.MAX_VALUE, min_index=-1; 

		for (int v = 0; v < V; v++) 
			if (sptSet[v] == false && dist[v] <= min) 
			{ 
				min = dist[v]; 
				min_index = v; 
			} 
	
		return min_index; 
	} 
	
	// دالة مساعدة لطباعة المصفوفة التي تم إنشاؤها
	void printSolution(int dist[], int n) 
	{ 
		System.out.println("Vertex Distance from Source"); 
		for (int i = 0; i < V; i++) 
			System.out.println(i+" tt "+dist[i]); 
	} 
	
	// تنفّذ الدالة خوارزمية دكسترا أحادية المصدر للعثور على
    // المسار الأقصر في رسم بياني ممثّل بواسطة مصفوفة المجاورة
	void dijkstra(int graph[][], int src) 
	{ 
		// مصفوفة المخرجات.
		// يمثل العنصر
		// dist[i]
		// i المسار الأقصر من المصدر إلى
 
		int dist[] = new int[V];
        
		// sptSet[i] will true if vertex i is included in shortest 
		// path tree or shortest distance from src to i is finalized 
		Boolean sptSet[] = new Boolean[V]; 
	
		// Initialize all distances as INFINITE and stpSet[] as false 
		for (int i = 0; i < V; i++) 
		{ 
			dist[i] = Integer.MAX_VALUE; 
			sptSet[i] = false; 
		} 
	
		// تكون المسافة بين الرأس المصدر ونفسه صفرًا دائمًا
		dist[src] = 0; 
	
		// العثور على المسار الأقصر لجميع الرؤوس
		for (int count = 0; count < V-1; count++) 
		{ 
			// اختيار الرأس ذي المسافة الأقصر من مجموعة الرؤوس التي لم تُعالج بعد.
			// في الدورة الأولى تكون
			// u == src 
			int u = minDistance(dist, sptSet); 
	
			// تعليم الرأس المنتخب على أنّه معالج
			sptSet[u] = true; 
	
			// تحديث قيمة المسافة للرؤوس المجاورة للرأس المنتخب
			for (int v = 0; v < V; v++) 
	
				// Update dist[v] only if is not in sptSet, there is an 
				// edge from u to v, and total weight of path from src to 
				// v through u is smaller than current value of dist[v] 
				if (!sptSet[v] && graph[u][v]!=0 && 
						dist[u] != Integer.MAX_VALUE && 
						dist[u]+graph[u][v] < dist[v]) 
					dist[v] = dist[u] + graph[u][v]; 
		} 
	
		// طباعة المصفوفة التي تم إنشاؤها
		printSolution(dist, V); 
	} 
	
	// اختبار الدوال السابقة 
	public static void main (String[] args) 
	{ 
		/* إنشاء الرسم البياني الوارد في المثال أعلاه */
	int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
								{4, 0, 8, 0, 0, 0, 0, 11, 0}, 
								{0, 8, 0, 7, 0, 4, 0, 0, 2}, 
								{0, 0, 7, 0, 9, 14, 0, 0, 0}, 
								{0, 0, 0, 9, 0, 10, 0, 0, 0}, 
								{0, 0, 4, 14, 10, 0, 2, 0, 0}, 
								{0, 0, 0, 0, 0, 2, 0, 1, 6}, 
								{8, 11, 0, 0, 0, 0, 1, 0, 7}, 
								{0, 0, 2, 0, 0, 0, 6, 7, 0} 
								}; 
		ShortestPath t = new ShortestPath(); 
		t.dijkstra(graph, 0); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14

ملاحظات:

1. تحسب الشيفرة المسافة الأقصر، ولكنّها لا تحسب المعلومات المرتبطة بالمسار، ولكن يمكن استخدام مصفوفة أبوية parent array وتحديثها عند تحديث المسافة واستخدامها لعرض المسار الأقصر من مصدر معين إلى رؤوس مختلفة.
2. تعمل هذه الشيفرة على الرسوم البيانية غير الموجّهة، ولكن يمكن استخدام الدالة نفسها مع الرسوم البيانية الموجّهة.
3. تعثر الشيفرة على المسافة الأقصر بين مصدر معين وجميع الرؤوس في الرسم البياني. إن كان المطلوب العثور على المسافة التي تربط بين مصدر معين وبين رأس واحد فقط، يمكن قطع الحلقة التكرارية عندما يكون الرأس المنتخب مساويًا للهدف المطلوب. (الخطوة 3.1 في خطوات الخوارزمية أعلاه).
4. لا يمكن استخدام خوارزمية ديكسترا مع الرسوم البيانية التي تكون أوزان أضلاعها ذات قيم سالبة، ولكن يمكن استخدام خوارزمية بيلمان-فورد في مثل هذه الحالة.

الرسوم البيانية الممثلة بواسطة قائمة المجاورة

إذا استخدمت قائمة المجاورة لتمثيل الرسم البياني فإن من الممكن التنقل عبر جميع الرؤوس في الرسم البياني باستخدام خوارزمية البحث بالعرض أولًا Breadth First Search وبتعقيد زمني قدره O(V+E)‎.

تتنقل هذه الطريقة عبر جميع الرؤوس في الرسم البياني باستخدام خورازمية البحث بالعرض أولًا، وتستخدم الكومة الصغرى Min Heap لتخزين الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر SPT (أو الرؤوس التي لم تُحسب المسافة الأقصر لها بعد). تستخدم الكومة الصغرى كرتل أولوية priority queue للحصول على الرأس ذي المسافة الأقصر من مجموعة الرؤوس غير المضافة بعد إلى شجرة المسار الأقصر. ويؤدي كل ذلك إلى تخفيض التعقيد الزمني لهذه العملية إلى O(Log V)‎.

يمكن تقسيم عمل الخوارزمية إلى الخطوات التالية:

1. إنشاء كومة صغرى حجمها V، وتمثّل V عدد الرؤوس الموجودة في الرسم البياني المعطى. تحتوي كل عقدة في الكومة الصغرى على رقم الرأس وقيمة المسافة لذلك الرأس.
2. تهيئة الكومة الصغرى باستخدام رأس مصدري كجذر للكومة، وتكون قيمة المسافة المسندة إلى الرأس المصدر هي 0 أما قيمة المسافة المسندة إلى بقية الرؤوس فتكون INF (ما لانهاية).
3. تؤدي الخوارزمية ما يلي بشرط أن لا تكون الكومة الصغرى فارغة:
   1. استخراج الرأس الذي يمتلك أصغر قيمة للمسافة من الكومة الصغرى، وليكن u.
   2. لكل رأس مجاور (ليكن v) للرأس u، يجري التحقق من أنّ v موجود في الكومة الصغرى. فإن كان كذلك، وكانت قيمة المسافة أكبر من وزن الضلع u-v مضافةً إليه قيمة المسافة للرأس u، فسنحدث قيمة المسافة للرأس v.

يمكن استخدام الشكل التالي لتوضيح الخطوات السابقة:

ليكن الرأس المصدر هو 0.

في البدء تكون قيمة المسافة للرأس المصدر هي 0 وتكون INF (ما لا نهاية) لبقية الرؤوس في الرسم البياني. لذا فإنّ الرأس المصدر سيُستخرج من الكومة الصغرى وسُتحدّث قيمة المسافة للرؤوس المجاورة للرأس 0 (وهما 1 و 7). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرأس 0.

الرؤوس الملونة باللون الأحمر هي الرؤوس التي تم الانتهاء من حساب قيمة المسافة الصغرى لها وهي خارج الكومة الصغرى.

لما كانت قيمة المسافة للرأس 1 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستُحدث قمية المسافة للرؤوس المجاورة للرأس 1 (تحدث قيمة المسافة إن كان الرأس غير موجود في الكومة الصغرى وكانت المسافة عبر الرأس 1 أقصر من المسافة السابقة). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرأسين 0 و 1.

لما كانت قيمة المسافة للرأس 7 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستحدث قيمة المسافة للرؤوس المجاورة (هما الرأسان 6 و 8). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرؤوس ‎0, 1, 7.

لما كانت قيمة المسافة للرأس 6 هي الأصغر من بين جميع العقد في الكومة الصغرى، فإنّها ستُستخرج من الكومة وستحدث قيمة المسافة للرؤوس المجاورة (هما الرأسان 5 و 8). تحتوي الكومة الصغرى الآن على جميع الرؤوس باستثناء الرؤوس ‎0, 1, 7, 6‎.

تُكرّر الخطوات السابقة إلى أن تصبح الكومة فارغة، ونحصل في النهاية على شجرة المسار الأقصر:

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية ديكسترا باستخدام الرسم البياني الممثل بواسطة قائمة المجاورة، وفي عدد من لغات البرمجة:

• C++‎:

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 

// تمثيل العقدة في قائمة المجاورة
struct AdjListNode 
{ 
	int dest; 
	int weight; 
	struct AdjListNode* next; 
}; 

// تمثيل عقدة المجاورة 
struct AdjList 
{ 
	struct AdjListNode *head; // مؤشر إلى عدة الرأس في القائمة
}; 


// تمثيل الرسم البياني. الرسم البياني هو مصفوفة من قوائم المجاورة
// V حجم المصفوفة سيكون
// (عدد الرؤوس في الرسم البياني)
struct Graph 
{ 
	int V; 
	struct AdjList* array; 
}; 

// دالة مساعدة لإنشاء عقدة قائمة مجاورة جديدة
struct AdjListNode* newAdjListNode(int dest, int weight) 
{ 
	struct AdjListNode* newNode = 
			(struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
	newNode->dest = dest; 
	newNode->weight = weight; 
	newNode->next = NULL; 
	return newNode; 
} 

// دالة مساعدة لإنشاء الرسم البياني يضم العدد المعطى من الرؤوس
struct Graph* createGraph(int V) 
{ 
	struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
	graph->V = V; 

    // V إنشاء مصفوفة لقائمة المجاورة، وسيكون حجم المصفوفة
	graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

	// NULL تهيئة كل قائمة مجاورة لتكون فارغة وذلك بإعطاء الرأس القيمة 
	for (int i = 0; i < V; ++i) 
		graph->array[i].head = NULL; 

	return graph; 
} 

// تضيف الدالة ضلعًا إلى الرسم البياني غير الموجّه
void addEdge(struct Graph* graph, int src, int dest, int weight) 
{ 
	// إضافة ضلع من المصدر إلى الوجهة. تضاف عقدة جديدة إلى قائمة المجاورة الخاصة بالمصدر
    // تضاف العقدة في البداية
	struct AdjListNode* newNode = newAdjListNode(dest, weight); 
	newNode->next = graph->array[src].head; 
	graph->array[src].head = newNode; 

	// لما كان الرسم البياني غير موجّه، فإن الضلع سيضاف من الوجهة إلى المصدر أيضًا
    // Since graph is undirected, add an edge from dest to src also 
	newNode = newAdjListNode(src, weight); 
	newNode->next = graph->array[dest].head; 
	graph->array[dest].head = newNode; 
} 

// تمثيل عقدة في الكومة الصغرى
struct MinHeapNode 
{ 
	int v; 
	int dist; 
}; 

// تمثيل الكومة الصغرى
struct MinHeap 
{ 
	int size;	 // عدد عقد الكومة الموجودة حاليًا
	int capacity; // سعة الكومة الصغرى
	int *pos;	 //  decreaseKey() مطلوب من قبل الدالة
	struct MinHeapNode **array; 
}; 

// دال ةمساعدة لإنشاء عقدة كومة صغرى جديدة
struct MinHeapNode* newMinHeapNode(int v, int dist) 
{ 
	struct MinHeapNode* minHeapNode = 
		(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); 
	minHeapNode->v = v; 
	minHeapNode->dist = dist; 
	return minHeapNode; 
} 

// دالة مساعدة لإنشاء كومة صغرى
struct MinHeap* createMinHeap(int capacity) 
{ 
	struct MinHeap* minHeap = 
		(struct MinHeap*) malloc(sizeof(struct MinHeap)); 
	minHeap->pos = (int *)malloc(capacity * sizeof(int)); 
	minHeap->size = 0; 
	minHeap->capacity = capacity; 
	minHeap->array = 
		(struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*)); 
	return minHeap; 
} 

// دالة مساعدة للتبديل بين عقدتين في الكومة الصغرى
// تحتاج عملية التحويل إلى كومة إلى عملية التبديل هذه
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) 
{ 
	struct MinHeapNode* t = *a; 
	*a = *b; 
	*b = t; 
} 

// دالة قياسية لإنشاء الكومة باستخدام الموقع المعطى
// تحدث هذه الدالة كذلك موقع العقد عند التبديل بينها
// decreaseKey() الموقع مطلوب من قبل الدالة
void minHeapify(struct MinHeap* minHeap, int idx) 
{ 
	int smallest, left, right; 
	smallest = idx; 
	left = 2 * idx + 1; 
	right = 2 * idx + 2; 

	if (left < minHeap->size && 
		minHeap->array[left]->dist < minHeap->array[smallest]->dist ) 
	smallest = left; 

	if (right < minHeap->size && 
		minHeap->array[right]->dist < minHeap->array[smallest]->dist ) 
	smallest = right; 

	if (smallest != idx) 
	{ 
		// العقد التي تحتاج إلى تبديل في الكومة الصغرى
		MinHeapNode *smallestNode = minHeap->array[smallest]; 
		MinHeapNode *idxNode = minHeap->array[idx]; 

		// تبديل المواقع
		minHeap->pos[smallestNode->v] = idx; 
		minHeap->pos[idxNode->v] = smallest; 

		// تبديل العقد
		swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); 

		minHeapify(minHeap, smallest); 
	} 
} 

// دالة مساعدة للتحقق من أنّ الكومة الصغرى فارغة أو لا
int isEmpty(struct MinHeap* minHeap) 
{ 
	return minHeap->size == 0; 
} 

// دالة قياسية لاستخراج العقدة الصغرى من الكومة
struct MinHeapNode* extractMin(struct MinHeap* minHeap) 
{ 
	if (isEmpty(minHeap)) 
		return NULL; 

	// تخزين عقدة الجذر
	struct MinHeapNode* root = minHeap->array[0]; 

	// إحلال العقدة الأخيرة محل عقدة الجذر
	struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1]; 
	minHeap->array[0] = lastNode; 

	// تحديث موقع العقدة الأخيرة
	minHeap->pos[root->v] = minHeap->size-1; 
	minHeap->pos[lastNode->v] = 0; 

	// تقليص حجم الكومة وإنشاء كومة من الجذر
	--minHeap->size; 
	minHeapify(minHeap, 0); 

	return root; 
} 

// تستخدم هذه الدالة لإنقاص قيمة المسافة للرأس المعطى
// تستخدم هذه الدالة مصفوفة المواقع الخاصة بالكومة الصغرى للحصول على الموقع الحالي للعقدة في الكومة الصغرى
void decreaseKey(struct MinHeap* minHeap, int v, int dist) 
{ 
	// الحصول على موقع الرأس المعطى في مصفوفة الكومة
	int i = minHeap->pos[v]; 

	// الحصول على العقدة وتحديث قيمة المسافة الخاصة بها
	minHeap->array[i]->dist = dist; 

	// التنقل صعودًا ما لم تحوّل الشجرة الكاملة إلى كومة
	// O(Logn) التعقيد الزمني لهذه الحلقة التكرارية يبلغ
	while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist) 
	{ 
		// تبديل هذه العقدة بالعقدة الأب
		minHeap->pos[minHeap->array[i]->v] = (i-1)/2; 
		minHeap->pos[minHeap->array[(i-1)/2]->v] = i; 
		swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]); 

		// التحرك نحو موقع العقدة الأب
		i = (i - 1) / 2; 
	} 
} 

// دالة مساعدة للتحقق من وجود الرأس المعطى في الكومة الصغرى
bool isInMinHeap(struct MinHeap *minHeap, int v) 
{ 
if (minHeap->pos[v] < minHeap->size) 
	return true; 
return false; 
} 

// دالة مساعدة لطباعة الحل
void printArr(int dist[], int n) 
{ 
	printf("Vertex Distance from Source\n"); 
	for (int i = 0; i < n; ++i) 
		printf("%d \t\t %d\n", i, dist[i]); 
} 

// الدالة الرئيسية التي تحسب المسافات الخاصة بالمسارات الأقصر من المصدر إلى جميع الرؤوس
// O(ELogV) يبلغ التعقيد الزمني لهذه الدالة المقدار
void dijkstra(struct Graph* graph, int src) 
{ 
	int V = graph->V;// الحصول على عدد الرؤوس في الرسم البياني
	int dist[V];	 // قيم المسافة المستخدمة لانتخاب الضلع ذي الوزن الأقل

	// E تمثل الكومة الصغرى المجموعة
	struct MinHeap* minHeap = createMinHeap(V); 

	// تهيئة الكومة الصغرى مع جميع الرؤوس، وقيمة المسافة لجميع الرؤوس
	for (int v = 0; v < V; ++v) 
	{ 
		dist[v] = INT_MAX; 
		minHeap->array[v] = newMinHeapNode(v, dist[v]); 
		minHeap->pos[v] = v; 
	} 

	// جعل قيمة المسافة للرأس المصدر هي 0 ليكون أول رأس تستخرجه الخوارزمية
	minHeap->array[src] = newMinHeapNode(src, dist[src]); 
	minHeap->pos[src] = src; 
	dist[src] = 0; 
	decreaseKey(minHeap, src, dist[src]); 

	// V يساوي حجم الكومة الصغرى في البداية
	minHeap->size = V; 

	// في الحلقة التكرارية التالية تحتوي الكومة الصغرى على جميع العقد
    // التي لم يتم الانتهاء من حساب قيمة المسافة الأصغر لها
	while (!isEmpty(minHeap)) 
	{ 
		// استخراج الرأس الذي يمتلك أصغر قيمة للمسافة
		struct MinHeapNode* minHeapNode = extractMin(minHeap); 
		int u = minHeapNode->v; // تخزين رقم الرأس المستخرج

		// التنقل عبر جميع الرؤوس المجاورة للرأس المستخرج
        // وتحديث قيم المسافة لها
		struct AdjListNode* pCrawl = graph->array[u].head; 
		while (pCrawl != NULL) 
		{ 
			int v = pCrawl->dest; 

			// إن كانت قيمة المسافة الأقصر للرأس المجاور لم تحسب بعد، وكانت المسافة
            // عبر الرأس المجاور والرأس المستخرج أقل من قيمة المسافة المحسوبة سابقًا
			if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX && 
										pCrawl->weight + dist[u] < dist[v]) 
			{ 
				dist[v] = dist[u] + pCrawl->weight; 

				// تحديث قيمة المسافة في الكومة الصغرى كذلك
				decreaseKey(minHeap, v, dist[v]); 
			} 
			pCrawl = pCrawl->next; 
		} 
	} 

	// طباعة المسارات الأقصر التي جرى حسابها
	printArr(dist, V); 
} 


// اختبار الدوال السابقة
int main() 
{ 
	// إنشاء الرسم البياني المعروض في المثال أعلاه
	int V = 9; 
	struct Graph* graph = createGraph(V); 
	addEdge(graph, 0, 1, 4); 
	addEdge(graph, 0, 7, 8); 
	addEdge(graph, 1, 2, 8); 
	addEdge(graph, 1, 7, 11); 
	addEdge(graph, 2, 3, 7); 
	addEdge(graph, 2, 8, 2); 
	addEdge(graph, 2, 5, 4); 
	addEdge(graph, 3, 4, 9); 
	addEdge(graph, 3, 5, 14); 
	addEdge(graph, 4, 5, 10); 
	addEdge(graph, 5, 6, 2); 
	addEdge(graph, 6, 7, 1); 
	addEdge(graph, 6, 8, 6); 
	addEdge(graph, 7, 8, 7); 

	dijkstra(graph, 0); 

	return 0; 
}

• بايثون:

from collections import defaultdict 
import sys 

class Heap(): 

	def __init__(self): 
		self.array = [] 
		self.size = 0
		self.pos = [] 

	def newMinHeapNode(self, v, dist): 
		minHeapNode = [v, dist] 
		return minHeapNode 

	# دالة مساعدة للتبديل بين عقدتين
    # في الكومة الصغرى. هذه العملية مطلوبة من قبل عملية إنشاء الكومة
	def swapMinHeapNode(self,a, b): 
		t = self.array[a] 
		self.array[a] = self.array[b] 
		self.array[b] = t 

	# دالة قياسية لإنشاء الكومة عند الموقع المعطى
    # هذه الدالة تحدّث كذلك مواقع العقد
    # عند التبديل بينها
    # decreaseKey() المواقع مطلوبة من قبل الدالة
	def minHeapify(self, idx): 
		smallest = idx 
		left = 2*idx + 1
		right = 2*idx + 2

		if left < self.size and self.array[left][1] \ 
								< self.array[smallest][1]: 
			smallest = left 

		if right < self.size and self.array[right][1]\ 
								< self.array[smallest][1]: 
			smallest = right 

		# العقد التي يجب التبديل بينها في الكومة الصغرى
        # إن لم يكن الموقع هو الموقع الأصغر
		if smallest != idx: 

			# التبديل بين المواقع
			self.pos[ self.array[smallest][0] ] = idx 
			self.pos[ self.array[idx][0] ] = smallest 

			# التبديل بين العقد
			self.swapMinHeapNode(smallest, idx) 

			self.minHeapify(smallest) 

	# دالة قياسية لاستخراج العقدة الصغرى من الكومة
	def extractMin(self): 

		# الخروج من الدالة إن كانت الكومة فارغة
		if self.isEmpty() == True: 
			return

		# تخزين عقدة الجذر
		root = self.array[0] 

		# استبدال عقدة الجذر بالعقدة الأخيرة
		lastNode = self.array[self.size - 1] 
		self.array[0] = lastNode 

		# تحديث موقع العقدة الأخيرة
		self.pos[lastNode[0]] = 0
		self.pos[root[0]] = self.size - 1

		# تقليص حجم الكومة وإنشاء كومة من الجذر
		self.size -= 1
		self.minHeapify(0) 

		return root 

	def isEmpty(self): 
		return True if self.size == 0 else False

	def decreaseKey(self, v, dist): 

		# الحصول على موقع الرأس المعطى في مصفوفة الكومة

		i = self.pos[v] 

		# الحصول على العقدة وتحديث قيمة المسافة الخاصة بها
		self.array[i][1] = dist 

		# التنقل صعودًا ما لم تحوّل الشجرة الكاملة إلى كومة
        # O(Logn) يبلغ التعقيد الزمني لهذه الحلقة التكرارية المقدار
		while i > 0 and self.array[i][1] < self.array[(i - 1) / 2][1]: 

			# تبديل هذه العقدة مع العقدة الأب الخاصة بها
			self.pos[ self.array[i][0] ] = (i-1)/2
			self.pos[ self.array[(i-1)/2][0] ] = i 
			self.swapMinHeapNode(i, (i - 1)/2 ) 

			# التحرك إلى موقع العقدة الأب
			i = (i - 1) / 2; 

	# دالة مساعدة للتحق من أن الرأس المعطى موجود في الكومة الصغرى
	def isInMinHeap(self, v): 

		if self.pos[v] < self.size: 
			return True
		return False


def printArr(dist, n): 
	print "Vertex\tDistance from source"
	for i in range(n): 
		print "%d\t\t%d" % (i,dist[i]) 


class Graph(): 

	def __init__(self, V): 
		self.V = V 
		self.graph = defaultdict(list) 
	
    # تضيف الدالة ضلعًا إلى الرسم البياني غير الموجّه
	def addEdge(self, src, dest, weight): 

		# إضافة ضلع من المصدر إلى الوجهة
        # تضاف عقدة جديدة إلى قائمة المجاورة الخاصة بالمصدر.
        # تضاف العقدة في البداية
        # يمتلك العنصر الأول في العقدة الوجهة
        # ويمتلك العنصر الثاني وزن الضلع
		newNode = [dest, weight] 
		self.graph[src].insert(0, newNode) 

		# لما كان الرسم البياني غير موجّهٍ، فإنّ الضلع
        # سيضاف من الوجهة إلى المصدر كذلك
		newNode = [src, weight] 
		self.graph[dest].insert(0, newNode) 

	# الدالة الرئيسة التي تحسب المسافات
    # لأقصر المسارات من المصدر إلى جميع الرؤوس في الرسم البياني.
    # O(ELogV) يبلغ التعقيد الزمني لهذه الدالة المقدار
	def dijkstra(self, src): 

		V = self.V # الحصول على عدد الرؤوس في الرسم البياني
		dist = [] # قيم المسافة المستخدمة لانتخاب الضلع ذي الوزن الأقل 

		# E تمثل الكومة الصغرة المجموعة
		minHeap = Heap() 

		# تهيئة الكومة الصغرى مع جميع الرؤوس
        # قيمة المسافة لجميع الرؤوس
		for v in range(V): 
			dist.append(sys.maxint) 
			minHeap.array.append( minHeap.newMinHeapNode(v, dist[v]) ) 
			minHeap.pos.append(v) 

		# جعل قيمة المسافة للرأس المصدر هي 0
        # وذلك ليكون أول رأس يُستخرج من الكومة الصغرى
		minHeap.pos[src] = src 
		dist[src] = 0
		minHeap.decreaseKey(src, dist[src]) 

		# V يكون حجم الكومة الصغرى في البداية مساويًا لـ
		minHeap.size = V; 

		# في الحلقة التكرارية التالية، تحتوي الكومة الصغرى على جميع العقد
        # التي لم يتم الانتهاء من حساب قيمة المسافة الأقصر لها
		while minHeap.isEmpty() == False: 

			# استخراج الرأس مع قيمة المسافة الأقصر
			newHeapNode = minHeap.extractMin() 
			u = newHeapNode[0] 

			# التنقل عبر جميع الرؤوس المجاورة للرأس المعطى
            # وتحديث قيم المسافات الخاصة بها
			for pCrawl in self.graph[u]: 

				v = pCrawl[0] 

				# إن كانت قيمة المسافة الأقصر للرأس المجاور غير محسوبة بعد
                # وكانت المسافة من الرأس المجاور إلى الرأس الحالي أقل
                # من المسافة المحسوبة سابقًا
				if minHeap.isInMinHeap(v) and dist[u] != sys.maxint and \ 
				pCrawl[1] + dist[u] < dist[v]: 
						dist[v] = pCrawl[1] + dist[u] 

						# نحدث قيمة المسافة
						# في الكومة الصغرى كذلك
						minHeap.decreaseKey(v, dist[v]) 

		printArr(dist,V) 


# اختبار الدوال السابقة
graph = Graph(9) 
graph.addEdge(0, 1, 4) 
graph.addEdge(0, 7, 8) 
graph.addEdge(1, 2, 8) 
graph.addEdge(1, 7, 11) 
graph.addEdge(2, 3, 7) 
graph.addEdge(2, 8, 2) 
graph.addEdge(2, 5, 4) 
graph.addEdge(3, 4, 9) 
graph.addEdge(3, 5, 14) 
graph.addEdge(4, 5, 10) 
graph.addEdge(5, 6, 2) 
graph.addEdge(6, 7, 1) 
graph.addEdge(6, 8, 6) 
graph.addEdge(7, 8, 7) 
graph.dijkstra(0)

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة التنفيذ الواردة أعلاه المقدار O(V^2)‎. ويمكن تخفيض هذا المقدار إلى O(E Log V)‎ إذا كان الرسم البياني ممثلًا بواسطة قائمة المجاورة وذلك بالاستعانة بالكومة الثنائية.

أسلوب الخوارزمية

هذه الخوارزمية تتبع أسلوب الخوارزميات الجشعة Greedy Algorithms.

مصادر

• صفحة Bellman–Ford Algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Floyd Warshall Algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Dijkstra’s shortest path algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Dijkstra’s Algorithm for Adjacency List Representation في توثيق الخوارزميات في موقع GeeksforGeeks.

تعديل المقال