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

خوارزمية فلويد-مارشل هي مثال على البرمجة الديناميكية. الاسم مقتبس من روبرت فلويد في 1962 ولاحقا انضم ستيفن ورشيل لوجود الإغلاق المتعدد للرسم. الخورامية تسمى أيضًا: خوارزمية فلويد، خوارزمية روي ورشل، خوارزمية روي فلويد.

الخوارزمية تقارن جميع الطرق الممكنة في رسمة. يكون من خلال مقارنة في رسمة.

السودو كود لهذه الخوارزمية هو كالتالي:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

إيجاد أقصر طريق في رسمة مباشرة (Directed graph) الإغلاق المتعدد للرسمة المباشرة (Transitive closure of directed graph) إيجاد التعبير النمطي في لغة اعتيادية انعاكس المصفوفات الحقيقي

• بوابة علم الحاسوب