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


مستوى الصعوبة متوسط
كثيرا ما يطلب في فيسبوك Qualtrics
البرمجة الديناميكية رسم بياني أقصر الطرق

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

الآن ، قد يقول القارئ:

لدينا ديكسترا سابقا. لماذا ننزعج أنفسنا بخوارزمية أخرى؟ اسمحوا لي أن أرضي مثل هذه الاستفسارات مع عيوب Dijkstra

  • إنه جشع!
  • لا يمكن أن تعمل مع الأوزان السلبية
  • قد يعطي أو لا يعطي إجابة صحيحة.

وبالتالي ، نهدف في هذا المقال إلى تغطية:

  • كيف تعمل خوارزمية بيلمان فورد؟
  • عيوب خوارزمية بيلمان فورد.

كيف تعمل خوارزمية بيلمان فورد؟

بالنسبة للرؤوس n ، نقوم بإرخاء الحواف لـ n-1 مرات حيث n هو عدد الحواف. دعنا الآن ننظر في معادلة الاسترخاء التي هو أهم شيء في هذه الخوارزمية.

الاسترخاء (ش ، ت):

إذا كانت المسافة (v)> المسافة (ش) + التكلفة (ش ، ت):

المسافة (ت) = المسافة (ش) + التكلفة (ش ، ت)

حيث u و v حواف.

الآن بعد أن عرفنا معادلة الاسترخاء ، دعنا ننتقل إلى الخوارزمية خطوة بخطوة-

  • تهيئة المسافة من المصدر إلى الوجهة على أنها ما لا نهاية.
  • حدد أي حافتين وقم بعمل قائمة من الحواف.
  • قم بإرخاء الحواف حتى تبدأ أقصر مسافة في تكرار نفسها أو في أسوأ سيناريو n-1 مرات.

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

دعونا نفهم هذا بشكل أفضل بالقدوة. في الرسم البياني أدناه ، المصدر = 0 ، عدد الرؤوس = 5

في البداية ، قمنا بتعيين جميع المسافات على أنها لا نهائية ونقوم بعمل قائمة بالحواف

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

للاسترخاء لـ (0,1،0) لدينا 2 + 1 <∞ مما يجعلنا نقوم بتحديث القيمة عند 2 كـ XNUMX ، كما نقوم بإرخاء جميع الحواف بالمثل.

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

سيكون هذا هو الرسم البياني الذي تم الحصول عليه بعد التكرار الأول

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

وبالمثل ، سنقوم بمعالجة الرسم البياني 5 مرات للوصول إلى الرسم البياني النهائي بأقل مسافات نحصل عليها كما هو موضح في الرسم البياني أدناه.

الآن بعد أن فهمنا كيفية عمل الخوارزمية ، دعونا ننفذها باستخدام الكود

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

import java.util.*;
class bellman
{
  public static void bell(int graph[][],int V,int E,int src)
  {
    int []distance=new int[V];
    //Initializing the distance to 1 for all the vertices
    for(int i=1;i<V;i++)
      distance[i]=Integer.MAX_VALUE;
    //Relaxing all the edges V-1 times
    for(int i=0;i<V;i++)
    {
      for(int j=0;j<E;j++)
      {      //dist(v)+cost(u,v)<dist(v)
        if(distance[graph[j][0]]+graph[j][2]<distance[graph[j][1]])
        {
          distance[graph[j][1]]=distance[graph[j][0]]+graph[j][2];
        }
      }
    }
    //Checking for negative weight cycle
    for(int i=0;i<E;i++)
    {
      int start=graph[i][0];
      int desti=graph[i][1];
      int cost=graph[i][2];
      if(distance[start]!=Integer.MAX_VALUE && distance[start]+cost<distance[desti])
        System.out.println("Negative weight cycle detected");
    }
    for(int i=0;i<V;i++)
    {
      System.out.println("Shortest distance from 0 to:"+i+" is "+distance[i]);
    }
    
  }
  public static void main(String args[])
  {
    int V=5;
    int E=7;
    int graph[][]={{0,1,2},{0,3,1},{0,2,6},
    {1,3,3},{1,4,6},
    {2,4,1},
    {3,4,5}};
    bell(graph,V,E,0);
  } 
}

كود C ++

#include <bits/stdc++.h> 
struct Edge 
{ 
    int src, dest, weight; 
}; 

struct Graph 
{ 
    int V, E; 
    struct Edge* edge; 
}; 

struct Graph* create(int V, int E) 
{ 
    struct Graph* graph = new Graph; 
    graph->V = V; 
    graph->E = E; 
    graph->edge = new Edge[E]; 
    return graph; 
} 
void chkres(int dist[], int n) 
{ 
    printf("Vertex   Distance from\n"); 
    for (int i = 0; i < n; ++i) 
        printf("%d \t %d\n", i, dist[i]); 
} 
  
void BellmanFord(struct Graph* graph, int src) 
{ 
    int V = graph->V; 
    int E = graph->E; 
    int dist[V]; 
    //Initalizing to infinity
    for (int i = 0; i < V; i++) 
        dist[i] = INT_MAX; 
    dist[src] = 0; 
  
    //Relaxing all edges |V| - 1 times.
    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");
            return;
        } 
    } 
    chkres(dist, V); 
    return; 
} 
  
int main() 
{
    int V = 4; 
    int E = 4;
    struct Graph* graph = create(V, E); 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 
    graph->edge[0].weight = 3; 
    graph->edge[1].src = 0; 
    graph->edge[1].dest = 2; 
    graph->edge[1].weight = -2;
    graph->edge[2].src = 1; 
    graph->edge[2].dest = 2; 
    graph->edge[2].weight = 1; 
    graph->edge[3].src = 1; 
    graph->edge[3].dest = 3; 
    graph->edge[3].weight = 0; 
    BellmanFord(graph, 0); 
  
    return 0; 
}
Vertex   Distance from
0 	 0
1 	 3
2 	 -2
3 	 3

تحليل التعقيد

يلخص التعقيد الزمني لهذه الخوارزمية حتى O (V * E) حيث V هو عدد الرؤوس و E هو عدد الحواف في رسم بياني.

المزايا والتطبيقات الواقعية 

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

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

  • يمكن أن تعمل فقط مع الرسوم البيانية الموجهة
  • يتطلب فقط معلومات محلية

المراجع