الگوریتم بلمن فورد چیست، آموزش و بررسی بلمن فورد

الگوریتم بلمن-فورد یکی از الگوریتم‌های مهم در حوزه علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است. است و برای پیدا کردن کوتاه ترین مسیر در یک گراف جهت دار وزن دار استفاده می‌شود. در این مقاله به بررسی این الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد، نحوه پیاده‌سازی و کاربردهای آن می‌پردازیم.

کاربرد الگوریتم بلمن-فورد

در ادامه به بررسی کاربردهای الگوریتم بلمن-فورد می‌پردازیم اما قبل از این‌که به آن بپردازیم، باید با گراف جهت دار وزن دار آشنا شویم. در تعریف ساده، گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... جهت‌دار وزن‌دار، گرافی است که هر یال آن یک جهت از مبدأ به مقصد و وزن مشخصی دارد. حال ببینیم الگوریتم بلمن-فورد، در کجا کاربرد دارد؟

پیدا کردن کوتاه ترین مسیر در گراف

یکی از مسائل مهم در گراف، پیدا کردن کوتاه‌ترین مسیر بین دو گره است. یکی از کاربردهای الگوریتم بلمن-فورد، پیدا کردن این مسیر است. در بخش زیر، ما مراحل این الگوریتم را به شکلی ساده توضیح می‌دهیم:

1. مقدار گره مبدأ را برابر 0 و مقدار بقیه گره‌های گراف را برابر یک مقدار بسیار بزرگ (معمولا بی‌نهایت) قرار می‌دهیم.
2. فاصله گره مبدأ تا گره v را با کمینه دو مقدار زیر به‌روز می‌کنیم (به این مرحله Relax کردن می‌گوییم):
   • فاصله گره مبدا تا گره u + وزن یال (u, v)
   • مقدار فعلی گره v
3. مرحله 2 را v-1 بار برای تمام گره‌ها انجام می‌دهیم که v تعداد رأس‌ها را نشان می‌دهد.

برای درک بهتر این الگوریتم، مثال زیر را درنظر بگیرید:

حال که گراف بالا را در نظر گرفتید، مراحل الگوریتم بلمن-فورد را به‌ترتیب روی این گراف انجام می‌دهیم:

1. در مرحله اول، مقدار گره A را برابر 0 و مقدار بقیه گره‌ها را برابر ‌بی‌نهایت قرار می‌دهیم.
   
2. مقادیر گره‌ها را Relax می‌کنیم.
3. از گره B شروع می‌کنیم. مقدار این گره را با کمینه مقادیر زیر جایگزین می‌کنیم:
   • مقدار گره A + وزن یال (A, B) که این مقدار برابر 0+1=1 می‌شود.
   • مقدار گره B که این مقدار برابر بی‌نهایت است.
   • مقدار B برابر 1 خواهد شد.
4. برای گره C داریم:
   • مقدار گره B + وزن یال (B, C) که این مقدار برابر 1+2=3 می‌شود.
   • مقدار گره C که این مقدار برابر بی‌نهایت است.
   • مقدار گره C برابر 3 خواهد شد.
5. برای گره D داریم:
   • مقدار گره B + وزن یال (B, D) که این مقدار برابر 1+3=4 می‌شود.
   • مقدار گره C + وزن یال (C, D) که این مقدار برابر 3+4=7 می‌شود.
   • مقدار گره D که این مقدار برابر بی‌نهایت است.
   • مقدار گره D برابر 4 می‌شود.

با توجه به این که 4 گره داریم، مرحله 2 را 2 بار دیگر هم انجام می‌دهیم (یعنی 1-4=3 بار در مجموع) و پس از انجام این مراحل، کوتاه‌ترین مسیر از گره A به بقیه گره‌ها پیدا خواهد شد.

پیدا کردن دور منفی

دور منفی در گراف به این معنی است که در یک دور، مجموع وزن یال‌های تشکیل دهنده آن دور، منفی است. الگوریتم بلمن-فورد قابلیت بررسی اینکه آیا چنین دوری در گراف وجود دارد یا خیر را دارد. برای تشخیص اینکه چنین دوری وجود دارد یا خیر، v بار الگوریتم بلمن-فورد را اجرا می‌کنیم که v نشان‌دهنده تعداد گره‌های گراف است. اگر در اجرای آخر مقادیر گره‌ها تغییری نکرد، گراف دور منفی ندارد؛ ولی اگر مقدار گره‌ای تغییر کرد، از آن گره شروع کرده و به ترتیب پدران آن گره را پیدا می‌کنیم تا جایی که به خود گره برسیم. این دور، دور منفی گراف است.

پیاده سازی الگوریتم بلمن-فورد

حالا که با الگوریتم بلمن-فورد آشنا شدیم و مراحل کارکرد آن را بررسی کردیم، وقت آن است که به پیاده‌سازی این الگوریتم بپردازیم.

Pseudo Code

برای پیاده سازی الگوریتم بلمن-فورد لازم داریم که طول مسیر هرکدام از گره‌ها از گره مبدأ را داشته باشیم. می‌توان این مقادیر را در یک آرایه با اندازه v پیاده کنیم. همین‌طور ما لازم داریم که کوتاه‌ترین مسیر را بیابیم، نه فقط کوتاه‌ترین فاصله را؛ برای همین باید گره‌هایی که در طول مسیر هستند را به‌ترتیب ذخیره کنیم. شبه کد زیر پیاده سازی الگوریتم بلمن-فورد را نشان می‌دهد:

function bellmanFord(G, S)
  for each vertex V in G
    distance[V] - infinite
      previous[V] - NULL
  distance[S] - 0

  for each vertex V in G				
    for each edge (U,V) in G
      tempDistance - distance[U] + edge_weight(U, V)
      if tempDistance  distance[V]
        distance[V] - tempDistance
        previous[V] - U

  for each edge (U,V) in G
    If distance[U] + edge_weight(U, V)  distance[V}
      Error: Negative Cycle Exists

  return distance[], previous[]

function bellmanFord(G, S)
  for each vertex V in G
    distance[V] - infinite
      previous[V] - NULL
  distance[S] - 0

  for each vertex V in G				
    for each edge (U,V) in G
      tempDistance - distance[U] + edge_weight(U, V)
      if tempDistance  distance[V]
        distance[V] - tempDistance
        previous[V] - U

  for each edge (U,V) in G
    If distance[U] + edge_weight(U, V)  distance[V}
      Error: Negative Cycle Exists

  return distance[], previous[]

کپی کردن کد

حالا که با شبه کد الگوریتم بلمن-فورد آشنا شدیم، این الگوریتم را با زبان های برنامه نویسیزبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مختلف پیاده‌سازی می‌کنیم.

Python

# Bellman Ford Algorithm in Python


class Graph:

  def __init__(self, vertices):
    self.V = vertices   # Total number of vertices in the graph
    self.graph = []     # Array of edges

  # Add edges
  def add_edge(self, s, d, w):
    self.graph.append([s, d, w])

  # Print the solution
  def print_solution(self, dist):
    print(“Vertex Distance from Source”)
    for I in range(self.V):
      print(“{0}\t\t{1}”.format(I, dist[i]))

  def bellman_ford(self, src):

    # Step 1: fill the distance array and predecessor array
    dist = [float(“Inf”)] * self.V
    # Mark the source vertex
    dist[src] = 0

    # Step 2: relax edges |V| - 1 times
    for _ in range(self.V – 1):
      for s, d, w in self.graph:
        if dist[s] != float(“Inf”) and dist[s] + w  dist[d]:
          dist[d] = dist[s] + w

    # Step 3: detect negative cycle
    # if value changes then we have a negative cycle in the graph
    # and we cannot find the shortest distances
      for s, d, w in self.graph:
        if dist[s] != float(“Inf”) and dist[s] + w  dist[d]:
          print(“Graph contains negative weight cycle”)
          return

    # No negative weight cycle found!
    # Print the distance and predecessor array
    self.print_solution(dist)


g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)

g.bellman_ford(0)

# Bellman Ford Algorithm in Python

class Graph:

  def __init__(self, vertices):
    self.V = vertices   # Total number of vertices in the graph
    self.graph = []     # Array of edges

  # Add edges
  def add_edge(self, s, d, w):
    self.graph.append([s, d, w])

  # Print the solution
  def print_solution(self, dist):
    print(“Vertex Distance from Source”)
    for I in range(self.V):
      print(“{0}\t\t{1}”.format(I, dist[i]))

  def bellman_ford(self, src):

    # Step 1: fill the distance array and predecessor array
    dist = [float(“Inf”)] * self.V
    # Mark the source vertex
    dist[src] = 0

    # Step 2: relax edges |V| - 1 times
    for _ in range(self.V – 1):
      for s, d, w in self.graph:
        if dist[s] != float(“Inf”) and dist[s] + w  dist[d]:
          dist[d] = dist[s] + w

    # Step 3: detect negative cycle
    # if value changes then we have a negative cycle in the graph
    # and we cannot find the shortest distances
      for s, d, w in self.graph:
        if dist[s] != float(“Inf”) and dist[s] + w  dist[d]:
          print(“Graph contains negative weight cycle”)
          return

    # No negative weight cycle found!
    # Print the distance and predecessor array
    self.print_solution(dist)


g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)

g.bellman_ford(0)

کپی کردن کد

Java

// Bellman Ford Algorithm in Java

class CreateGraph {

  // CreateGraph - it consists of edges
  class CreateEdge {
    int s, d, w;

    CreateEdge() {
      s = d = w = 0;
    }
  };

  int V, E;
  CreateEdge edge[];

  // Creates a graph with V vertices and E edges
  CreateGraph(int v, int e) {
    V = v;
    E = e;
    edge = new CreateEdge[e];
    for (int i = 0; i < e; ++i)
      edge[i] = new CreateEdge();
  }

  void BellmanFord(CreateGraph graph, int s) {
    int V = graph.V, E = graph.E;
    int dist[] = new int[V];

    // Step 1: fill the distance array and predecessor array
    for (int i = 0; i < V; ++i)
      dist[i] = Integer.MAX_VALUE;

    // Mark the source vertex
    dist[s] = 0;

    // Step 2: relax edges |V| - 1 times
    for (int i = 1; i < V; ++i) {
      for (int j = 0; j < E; ++j) {
        // Get the edge data
        int u = graph.edge[j].s;
        int v = graph.edge[j].d;
        int w = graph.edge[j].w;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
          dist[v] = dist[u] + w;
      }
    }

    // Step 3: detect negative cycle
    // if value changes then we have a negative cycle in the graph
    // and we cannot find the shortest distances
    for (int j = 0; j < E; ++j) {
      int u = graph.edge[j].s;
      int v = graph.edge[j].d;
      int w = graph.edge[j].w;
      if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
        System.out.println("CreateGraph contains negative w cycle");
        return;
      }
    }

    // No negative w cycle found!
    // Print the distance and predecessor array
    printSolution(dist, V);
  }

  // Print the solution
  void printSolution(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; // Total vertices
    int E = 8; // Total Edges


    CreateGraph graph = new CreateGraph(V, E);


    // edge 0 --> 1
    graph.edge[0].s = 0;
    graph.edge[0].d = 1;
    graph.edge[0].w = 5;

    // edge 0 --> 2
    graph.edge[1].s = 0;
    graph.edge[1].d = 2;
    graph.edge[1].w = 4;

    // edge 1 --> 3
    graph.edge[2].s = 1;
    graph.edge[2].d = 3;
    graph.edge[2].w = 3;

    // edge 2 --> 1
    graph.edge[3].s = 2;
    graph.edge[3].d = 1;
    graph.edge[3].w = 6;

    // edge 3 --> 2
    graph.edge[4].s = 3;
    graph.edge[4].d = 2;
    graph.edge[4].w = 2;

    graph.BellmanFord(graph, 0); // 0 is the source vertex
  }
}

// Bellman Ford Algorithm in Java

class CreateGraph {

  // CreateGraph - it consists of edges
  class CreateEdge {
    int s, d, w;

    CreateEdge() {
      s = d = w = 0;
    }
  };

  int V, E;
  CreateEdge edge[];

  // Creates a graph with V vertices and E edges
  CreateGraph(int v, int e) {
    V = v;
    E = e;
    edge = new CreateEdge[e];
    for (int i = 0; i < e; ++i)
      edge[i] = new CreateEdge();
  }

  void BellmanFord(CreateGraph graph, int s) {
    int V = graph.V, E = graph.E;
    int dist[] = new int[V];

    // Step 1: fill the distance array and predecessor array
    for (int i = 0; i < V; ++i)
      dist[i] = Integer.MAX_VALUE;

    // Mark the source vertex
    dist[s] = 0;

    // Step 2: relax edges |V| - 1 times
    for (int i = 1; i < V; ++i) {
      for (int j = 0; j < E; ++j) {
        // Get the edge data
        int u = graph.edge[j].s;
        int v = graph.edge[j].d;
        int w = graph.edge[j].w;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
          dist[v] = dist[u] + w;
      }
    }

    // Step 3: detect negative cycle
    // if value changes then we have a negative cycle in the graph
    // and we cannot find the shortest distances
    for (int j = 0; j < E; ++j) {
      int u = graph.edge[j].s;
      int v = graph.edge[j].d;
      int w = graph.edge[j].w;
      if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
        System.out.println("CreateGraph contains negative w cycle");
        return;
      }
    }

    // No negative w cycle found!
    // Print the distance and predecessor array
    printSolution(dist, V);
  }

  // Print the solution
  void printSolution(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; // Total vertices
    int E = 8; // Total Edges


    CreateGraph graph = new CreateGraph(V, E);


    // edge 0 --> 1
    graph.edge[0].s = 0;
    graph.edge[0].d = 1;
    graph.edge[0].w = 5;

    // edge 0 --> 2
    graph.edge[1].s = 0;
    graph.edge[1].d = 2;
    graph.edge[1].w = 4;

    // edge 1 --> 3
    graph.edge[2].s = 1;
    graph.edge[2].d = 3;
    graph.edge[2].w = 3;

    // edge 2 --> 1
    graph.edge[3].s = 2;
    graph.edge[3].d = 1;
    graph.edge[3].w = 6;

    // edge 3 --> 2
    graph.edge[4].s = 3;
    graph.edge[4].d = 2;
    graph.edge[4].w = 2;

    graph.BellmanFord(graph, 0); // 0 is the source vertex
  }
}

کپی کردن کد

C

// Bellman Ford Algorithm in C

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

#define INFINITY 99999

//struct for the edges of the graph
struct Edge {
  int u;  //start vertex of the edge
  int v;  //end vertex of the edge
  int w;  //weight of the edge (u,v)
};

//Graph - it consists of edges
struct Graph {
  int V;        //total number of vertices in the graph
  int E;        //total number of edges in the graph
  struct Edge *edge;  //array of edges
};

void bellmanford(struct Graph *g, int source);
void display(int arr[], int size);

int main(void) {
  //create graph
  struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));
  g->V = 4;  //total vertices
  g->E = 5;  //total edges

  //array of edges for graph
  g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));

  //------- adding the edges of the graph
  /*
		edge(u, v)
		where 	u = start vertex of the edge (u,v)
				v = end vertex of the edge (u,v)
		
		w is the weight of the edge (u,v)
	*/

  //edge 0 --> 1
  g->edge[0].u = 0;
  g->edge[0].v = 1;
  g->edge[0].w = 5;

  //edge 0 --> 2
  g->edge[1].u = 0;
  g->edge[1].v = 2;
  g->edge[1].w = 4;

  //edge 1 --> 3
  g->edge[2].u = 1;
  g->edge[2].v = 3;
  g->edge[2].w = 3;

  //edge 2 --> 1
  g->edge[3].u = 2;
  g->edge[3].v = 1;
  g->edge[3].w = 6;

  //edge 3 --> 2
  g->edge[4].u = 3;
  g->edge[4].v = 2;
  g->edge[4].w = 2;

  bellmanford(g, 0);  //0 is the source vertex

  return 0;
}

void bellmanford(struct Graph *g, int source) {
  //variables
  int i, j, u, v, w;

  //total vertex in the graph g
  int tV = g->V;

  //total edge in the graph g
  int tE = g->E;

  //distance array
  //size equal to the number of vertices of the graph g
  int d[tV];

  //predecessor array
  //size equal to the number of vertices of the graph g
  int p[tV];

  //step 1: fill the distance array and predecessor array
  for (i = 0; i < tV; i++) {
    d[i] = INFINITY;
    p[i] = 0;
  }

  //mark the source vertex
  d[source] = 0;

  //step 2: relax edges |V| - 1 times
  for (i = 1; i <= tV - 1; i++) {
    for (j = 0; j < tE; j++) {
      //get the edge data
      u = g->edge[j].u;
      v = g->edge[j].v;
      w = g->edge[j].w;


      if (d[u] != INFINITY && d[v] > d[u] + w) {
        d[v] = d[u] + w;
        p[v] = u;
      }
    }
  }

  //step 3: detect negative cycle
  //if value changes then we have a negative cycle in the graph
  //and we cannot find the shortest distances
  for (i = 0; i < tE; i++) {
    u = g->edge[i].u;
    v = g->edge[i].v;
    w = g->edge[i].w;
    if (d[u] != INFINITY && d[v] > d[u] + w) {
      printf("Negative weight cycle detected!\n");
      return;
    }
  }

  //No negative weight cycle found!
  //print the distance and predecessor array
  printf("Distance array: ");
  display(d, tV);
  printf("Predecessor array: ");
  display(p, tV);
}

void display(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

// Bellman Ford Algorithm in C

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

#define INFINITY 99999

//struct for the edges of the graph
struct Edge {
  int u;  //start vertex of the edge
  int v;  //end vertex of the edge
  int w;  //weight of the edge (u,v)
};

//Graph - it consists of edges
struct Graph {
  int V;        //total number of vertices in the graph
  int E;        //total number of edges in the graph
  struct Edge *edge;  //array of edges
};

void bellmanford(struct Graph *g, int source);
void display(int arr[], int size);

int main(void) {
  //create graph
  struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));
  g->V = 4;  //total vertices
  g->E = 5;  //total edges

  //array of edges for graph
  g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));

  //------- adding the edges of the graph
  /*
		edge(u, v)
		where 	u = start vertex of the edge (u,v)
				v = end vertex of the edge (u,v)
		
		w is the weight of the edge (u,v)
	*/

  //edge 0 --> 1
  g->edge[0].u = 0;
  g->edge[0].v = 1;
  g->edge[0].w = 5;

  //edge 0 --> 2
  g->edge[1].u = 0;
  g->edge[1].v = 2;
  g->edge[1].w = 4;

  //edge 1 --> 3
  g->edge[2].u = 1;
  g->edge[2].v = 3;
  g->edge[2].w = 3;

  //edge 2 --> 1
  g->edge[3].u = 2;
  g->edge[3].v = 1;
  g->edge[3].w = 6;

  //edge 3 --> 2
  g->edge[4].u = 3;
  g->edge[4].v = 2;
  g->edge[4].w = 2;

  bellmanford(g, 0);  //0 is the source vertex

  return 0;
}

void bellmanford(struct Graph *g, int source) {
  //variables
  int i, j, u, v, w;

  //total vertex in the graph g
  int tV = g->V;

  //total edge in the graph g
  int tE = g->E;

  //distance array
  //size equal to the number of vertices of the graph g
  int d[tV];

  //predecessor array
  //size equal to the number of vertices of the graph g
  int p[tV];

  //step 1: fill the distance array and predecessor array
  for (i = 0; i < tV; i++) {
    d[i] = INFINITY;
    p[i] = 0;
  }

  //mark the source vertex
  d[source] = 0;

  //step 2: relax edges |V| - 1 times
  for (i = 1; i <= tV - 1; i++) {
    for (j = 0; j < tE; j++) {
      //get the edge data
      u = g->edge[j].u;
      v = g->edge[j].v;
      w = g->edge[j].w;


      if (d[u] != INFINITY && d[v] > d[u] + w) {
        d[v] = d[u] + w;
        p[v] = u;
      }
    }
  }

  //step 3: detect negative cycle
  //if value changes then we have a negative cycle in the graph
  //and we cannot find the shortest distances
  for (i = 0; i < tE; i++) {
    u = g->edge[i].u;
    v = g->edge[i].v;
    w = g->edge[i].w;
    if (d[u] != INFINITY && d[v] > d[u] + w) {
      printf("Negative weight cycle detected!\n");
      return;
    }
  }

  //No negative weight cycle found!
  //print the distance and predecessor array
  printf("Distance array: ");
  display(d, tV);
  printf("Predecessor array: ");
  display(p, tV);
}

void display(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

کپی کردن کد

C++

// Bellman Ford Algorithm in C++

#include <bits/stdc++.h>

// Struct for the edges of the graph
struct Edge {
  int u;  //start vertex of the edge
  int v;  //end vertex of the edge
  int w;  //w of the edge (u,v)
};

// Graph – it consists of edges
struct Graph {
  int V;        // Total number of vertices in the graph
  int E;        // Total number of edges in the graph
  struct Edge* edge;  // Array of edges
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
  struct Graph* graph = new Graph;
  graph->V = V;  // Total Vertices
  graph->E = E;  // Total edges

  // Array of edges for graph
  graph->edge = new Edge[E];
  return graph;
}

// Printing the solution
void printArr(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void BellmanFord(struct Graph* graph, int u) {
  int V = graph->V;
  int E = graph->E;
  int dist[V];

  // Step 1: fill the distance array and predecessor array
  for (int I = 0; I < V; i++)
    dist[i] = INT_MAX;

  // Mark the source vertex
  dist[u] = 0;

  // Step 2: relax edges |V| - 1 times
    for (int i = 1; i <= V - 1; i++) {
    for (int j = 0; j < E; j++) {
      // Get the edge data
      int u = graph->edge[j].u;
      int v = graph->edge[j].v;
      int w = graph->edge[j].w;
      if (dist[u] != INT_MAX && dist[u] + w < dist[v])
        dist[v] = dist[u] + w;
    }
  }

  // Step 3: detect negative cycle
  // if value changes then we have a negative cycle in the graph
  // and we cannot find the shortest distances
  for (int i = 0; i < E; i++) {
    int u = graph->edge[i].u;
    int v = graph->edge[i].v;
    int w = graph->edge[i].w;
    if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
      printf("Graph contains negative w cycle");
      return;
    }
  }


  // No negative weight cycle found!
  // Print the distance and predecessor array
  printArr(dist, V);


  return;
}


int main() {
  // Create a graph
  int V = 5;  // Total vertices
  int E = 8;  // Total edges


  // Array of edges for graph
  struct Graph* graph = createGraph(V, E);


  //------- adding the edges of the graph
  /*
		edge(u, v)
		where 	u = start vertex of the edge (u,v)
				v = end vertex of the edge (u,v)
		
		w is the weight of the edge (u,v)
	*/


  //edge 0 --> 1
  graph->edge[0].u = 0;
  graph->edge[0].v = 1;
  graph->edge[0].w = 5;


  //edge 0 --> 2
  graph->edge[1].u = 0;
  graph->edge[1].v = 2;
  graph->edge[1].w = 4;


  //edge 1 --> 3
  graph->edge[2].u = 1;
  graph->edge[2].v = 3;
  graph->edge[2].w = 3;


  //edge 2 --> 1
  graph->edge[3].u = 2;
  graph->edge[3].v = 1;
  graph->edge[3].w = 6;


  //edge 3 --> 2
  graph->edge[4].u = 3;
  graph->edge[4].v = 2;
  graph->edge[4].w = 2;


  BellmanFord(graph, 0);  //0 is the source vertex


  return 0;
}

// Bellman Ford Algorithm in C++

#include <bits/stdc++.h>

// Struct for the edges of the graph
struct Edge {
  int u;  //start vertex of the edge
  int v;  //end vertex of the edge
  int w;  //w of the edge (u,v)
};

// Graph – it consists of edges
struct Graph {
  int V;        // Total number of vertices in the graph
  int E;        // Total number of edges in the graph
  struct Edge* edge;  // Array of edges
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
  struct Graph* graph = new Graph;
  graph->V = V;  // Total Vertices
  graph->E = E;  // Total edges

  // Array of edges for graph
  graph->edge = new Edge[E];
  return graph;
}

// Printing the solution
void printArr(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void BellmanFord(struct Graph* graph, int u) {
  int V = graph->V;
  int E = graph->E;
  int dist[V];

  // Step 1: fill the distance array and predecessor array
  for (int I = 0; I < V; i++)
    dist[i] = INT_MAX;

  // Mark the source vertex
  dist[u] = 0;

  // Step 2: relax edges |V| - 1 times
    for (int i = 1; i <= V - 1; i++) {
    for (int j = 0; j < E; j++) {
      // Get the edge data
      int u = graph->edge[j].u;
      int v = graph->edge[j].v;
      int w = graph->edge[j].w;
      if (dist[u] != INT_MAX && dist[u] + w < dist[v])
        dist[v] = dist[u] + w;
    }
  }

  // Step 3: detect negative cycle
  // if value changes then we have a negative cycle in the graph
  // and we cannot find the shortest distances
  for (int i = 0; i < E; i++) {
    int u = graph->edge[i].u;
    int v = graph->edge[i].v;
    int w = graph->edge[i].w;
    if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
      printf("Graph contains negative w cycle");
      return;
    }
  }


  // No negative weight cycle found!
  // Print the distance and predecessor array
  printArr(dist, V);


  return;
}


int main() {
  // Create a graph
  int V = 5;  // Total vertices
  int E = 8;  // Total edges


  // Array of edges for graph
  struct Graph* graph = createGraph(V, E);


  //------- adding the edges of the graph
  /*
		edge(u, v)
		where 	u = start vertex of the edge (u,v)
				v = end vertex of the edge (u,v)
		
		w is the weight of the edge (u,v)
	*/


  //edge 0 --> 1
  graph->edge[0].u = 0;
  graph->edge[0].v = 1;
  graph->edge[0].w = 5;


  //edge 0 --> 2
  graph->edge[1].u = 0;
  graph->edge[1].v = 2;
  graph->edge[1].w = 4;


  //edge 1 --> 3
  graph->edge[2].u = 1;
  graph->edge[2].v = 3;
  graph->edge[2].w = 3;


  //edge 2 --> 1
  graph->edge[3].u = 2;
  graph->edge[3].v = 1;
  graph->edge[3].w = 6;


  //edge 3 --> 2
  graph->edge[4].u = 3;
  graph->edge[4].v = 2;
  graph->edge[4].w = 2;


  BellmanFord(graph, 0);  //0 is the source vertex


  return 0;
}

کپی کردن کد

پیچیدگی زمانی الگوریتم بلمن-فورد

در الگوریتم بلمن-فورد، ما در هر مرحله Relaxation، به تعداد یال‌ها (E)Relaxation را انجام می‌دهیم. تعداد دفعات تکرار مرحله Relaxation برابر تعداد گره‌های (V) گراف است. با توجه به این، پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده  این الگوریتم، O(E*V) است.

مقایسه الگوریتم بلمن-فورد با الگوریتم دایجسترا

• الگوریتم بلمن-فورد در هنگام وجود یال منفی هم به‌درستی کار می‌کند و توانایی شناسایی دور منفی را هم دارد ولی الگوریتم دایجستراالگوریتم دایجسترا (Dijkstra) از 0 تا 100 - الگوریتم دایکسترااین صفحه الگوریتم دایجسترا (Dijkstra) (یا همان الگوریتم دایکسترا) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم دایجسترا پرداخته است. در هنگام وجود یال منفی ممکن است درست کار کند یا نکند؛ ولی قطعاً توانایی شناسایی دور منفی را ندارد.
• پیچیدگی زمانی الگوریتم بلمن-فورد از مرتبه O(E*V) است. در حالی که پیچیدگی زمانی الگوریتم دایجسترا از مرتبه O(E*Log V) است. یعنی الگوریتم دایجسترا از لحاظ پیچیدگی زمانی از الگوریتم بلمن-فورد بهتر است.
• الگوریتم بلمن-فورد از روش برنامه نویسی پویابرنامه نویسی پویا چیست، برنامه نویسی پویا در طراحی الگوریتماین صفحه عالی به معرفی برنامه نویسی پویا یا Dynamic programming پرداخته و کاربردها و مثال هایی از برنامه نویسی پویا در طراحی الگوریتم آورده است  استفاده می‌کند ولی الگوریتم دایجسترا از روش حریصانه استفاده می‌کند.

جمع‌بندی

در این صفحه ما الگوریتم بلمن-فورد، که یکی از مهم‌ترین الگوریتم‌های مبحث گراف است را بررسی کردیم. این الگوریتم می‌تواند کوتاه‌ترین مسیر از یک مبدأ را در زمان O(E*V) پیدا کند؛ همچنین برخلاف الگوریتم دایجسترا، این الگوریتم توانایی پیدا کردن دور منفی در گراف را هم داراست. به علت این ویژگی مهم، این الگوریتم در بسیاری از تکنیک‌های مسیریابی کاربرد دارد.

مطالب مرتبط

همه مقالات

مرتب سازی ادغامی

گراف چیست،‌ آموزش تمامی مطالب گراف

آموزش نصب پایتون در ویندوز بصورت گام به گام و تصویری

چگونگی کار با فایل و فولدر در برنامه نویسی