Беллман Форд Алгоритм  


Кыйынчылык деңгээли орто
Көп суралган Facebook Qualtrics
Динамикалык программалоо график Кыска жол

Беллман Форд Algorithm булагы чокусунан бардык чокуларына эң кыска жолду табуу үчүн колдонулат. Булак төбөсү жана терс же оң болушу мүмкүн болгон четтеринин салмагы бар график берилген.

Эми, окурман мындай деп айтышы мүмкүн:

Бизде бар Dijkstra мурунтан эле. Эмне үчүн өзүбүздү башка алгоритм менен убара кылышыбыз керек? Мындай суроолорду канааттандырууга уруксат бериңиз Dijkstra кемчилиги

  • Бул ач көздүк!
  • Ал терс салмак менен иштей албайт
  • Туура жооп бере алат же бербейт.

Ошентип, бул макалада биз төмөнкүлөрдү камтууга багытталган:

  • Bellman Ford алгоритми кандайча иштейт?
  • Bellman Ford Алгоритминин кемчиликтери.

Bellman Ford Algorithm кантип иштейт?  

N чокулары үчүн, биз n-1 жолу четтерин эс алабыз, мында n - бул четтеринин саны. Келгиле эми эс алуу теңдемеси кайсы бул алгоритмдеги эң маанилүү нерсе.

Эс алуу (u, v):

эгер аралык (v)> аралык (u) + чыгым (u, v):

аралык (v) = аралык (u) + чыгым (u, v)

U жана v четтери бар.

Релаксация теңдемесин билгендиктен, алгоритмди этап-этабы менен карап чыгалы.

  • Булактан көздөгөн жерге чейинки аралыкты чексиздик катары баштаңыз.
  • Каалаган эки четиңизди тандап, четтеринин тизмесин түзүңүз.
  • Эң кыска аралык кайталана баштаганга чейин же эң начар сценарийде n-1 жолу четтерин бошотуңуз.

Bellman Ford Алгоритминин мисалы  

Келгиле, муну мисал аркылуу жакшыраак түшүнөбүз. Төмөндөгү графикте булак = 0, чокулардын саны = 5

ошондой эле
Эки Издөө дарагындагы эң төмөнкү жалпы ата-бабалар

Алгач бардык аралыктарды чексиздик катары белгилеп, четтеринин тизмесин түзөбүз

Беллман Форд Алгоритмтөөнөч

(0,1) үчүн эс алсак, бизде 0 + 2 <∞ маанисин 1 деп жаңыртууга аргасыз кылат, биз 2дин чектерин ушундай эле эс алабыз.

Беллман Форд Алгоритмтөөнөч

Бул биринчи кайталоодон кийин алынган график болмок

Беллман Форд Алгоритмтөөнөч

Биз төмөнкүдөй графикте көрсөтүлгөндөй эң аз аралыкта акыркы графикке жетүү үчүн графикти 5 жолу иштеп чыкмакпыз.

төөнөч Алгоритм кандай иштээрин түшүнгөндөн кийин, аны кодду колдонуп ишке ашыралы

Беллман Форд Алгоритминин Java Программасы  

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 - бул четтердин саны график.

ошондой эле
Бир нече массивди көбөйтүү иш-аракеттеринен кийин өзгөртүлгөн массивди басып чыгаруу

Артыкчылыктары жана чыныгы турмуштагы тиркемелер   

  • Терс салмак менен да иштейт. Бул кээ бир учурларда белгилүү бир жолду басып өтүүдөн кандайдыр бир артыкчылыкка ээ болгон учурда иштей алат. Мисал-крикет беттешине бара жатканда, салык төлөөгө туура келген жолдор жана туугандарыбыздын үйлөрү бар жолдор бар, алар үйүнө түшүп калсак, акча же белек бериши мүмкүн.
  • Бөлүштүрүлгөн тутумдар үчүн жакшы иштейт
  • Бул динамикалык алгоритми

Bellman Ford Алгоритминин кемчиликтери  

  • Ал багытталган графиктер үчүн гана иштей алат
  • Ал үчүн жергиликтүү маалымат гана талап кылынат

шилтемелер