একক উৎস সংক্ষিপ্ত পাথ অ্যালগরিদম (স্বেচ্ছাচারী ওজন ধনাত্মক বা নেতিবাচক জন্য) এছাড়াও পরিচিত বেলম্যান-ফোর্ড অ্যালগরিদম উৎস শীর্ষ থেকে অন্য কোনো শীর্ষে ন্যূনতম দূরত্ব খুঁজে পেতে ব্যবহৃত হয়। ডিজকস্ট্রার অ্যালগরিদমের সাথে এই অ্যালগরিদমের প্রধান পার্থক্য হল, ডিজকস্ট্রার অ্যালগরিদমে আমরা নেতিবাচক ওজন পরিচালনা করতে পারি না, তবে এখানে আমরা সহজেই এটি পরিচালনা করতে পারি।
বেলম্যান-ফোর্ড অ্যালগরিদম নীচের উপরে পদ্ধতিতে দূরত্ব খুঁজে পায়। প্রথমে এটি সেই দূরত্বগুলি খুঁজে পায় যেগুলির পথে কেবল একটি প্রান্ত রয়েছে। এর পরে সমস্ত সম্ভাব্য সমাধান খুঁজতে পথের দৈর্ঘ্য বাড়ান।
ইনপুট − গ্রাফের খরচ ম্যাট্রিক্স:
0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0
আউটপুট − উৎস ভার্টেক্স:2
ভার্ট:0 1 2 3 4
জেলা:-4 -2 0 3 -6
Pred:4 2 -1 0 1
গ্রাফের কোন ঋণাত্মক প্রান্ত চক্র নেই
অ্যালগরিদম
বেলম্যানফোর্ড(dist, pred, উৎস)
ইনপুট − দূরত্ব তালিকা, পূর্বসূরী তালিকা এবং উৎস শীর্ষবিন্দু।
আউটপুট - সত্য, যখন একটি নেতিবাচক চক্র পাওয়া যায়।
Begin iCount := 1 maxEdge := n * (n - 1) / 2 //n is number of vertices for all vertices v of the graph, do dist[v] := ∞ pred[v] := ϕ done dist[source] := 0 eCount := number of edges present in the graph create edge list named edgeList while iCount < n, do for i := 0 to eCount, do if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) pred[edgeList[i].v] := edgeList[i].u done done iCount := iCount + 1 for all vertices i in the graph, do if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i), then return true done return false End
উদাহরণ(C++)
#include<iostream> #include<iomanip> #define V 5 #define INF 999 using namespace std; //Cost matrix of the graph (directed) vertex 5 int costMat[V][V] = { {0, 6, INF, 7, INF}, {INF, 0, 5, 8, -4}, {INF, -2, 0, INF, INF}, {INF, INF, -3, 0, 9}, {2, INF, 7, INF, 0} }; typedef struct{ int u, v, cost; }edge; int isDiagraph(){ //check the graph is directed graph or not int i, j; for(i = 0; i<V; i++){ for(j = 0; j<V; j++){ if(costMat[i][j] != costMat[j][i]){ return 1;//graph is directed } } } return 0;//graph is undirected } int makeEdgeList(edge *eList){ //create edgelist from the edges of graph int count = -1; if(isDiagraph()){ for(int i = 0; i<V; i++){ for(int j = 0; j<V; j++){ if(costMat[i][j] != 0 && costMat[i][j] != INF){ count++;//edge find when graph is directed eList[count].u = i; eList[count].v = j; eList[count].cost = costMat[i][j]; } } } }else{ for(int i = 0; i<V; i++){ for(int j = 0; j<i; j++){ if(costMat[i][j] != INF){ count++;//edge find when graph is undirected eList[count].u = i; eList[count].v = j; eList[count].cost = costMat[i][j]; } } } } return count+1; } int bellmanFord(int *dist, int *pred,int src){ int icount = 1, ecount, max = V*(V-1)/2; edge edgeList[max]; for(int i = 0; i<V; i++){ dist[i] = INF;//initialize with infinity pred[i] = -1;//no predecessor found. } dist[src] = 0;//for starting vertex, distance is 0 ecount = makeEdgeList(edgeList); //edgeList formation while(icount < V){ //number of iteration is (Vertex - 1) for(int i = 0; i<ecount; i++){ if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){ //relax edge and set predecessor dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]; pred[edgeList[i].v] = edgeList[i].u; } } icount++; } //test for negative cycle for(int i = 0; i<ecount; i++){ if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){ return 1;//indicates the graph has negative cycle } } return 0;//no negative cycle } void display(int *dist, int *pred){ cout << "Vert: "; for(int i = 0; i<V; i++) cout <<setw(3) << i << " "; cout << endl; cout << "Dist: "; for(int i = 0; i<V; i++) cout << setw(3) << dist[i] << " "; cout << endl; cout << "Pred: "; for(int i = 0; i<V; i++) cout << setw(3) << pred[i] << " "; cout << endl; } int main(){ int dist[V], pred[V], source, report; source = 2; report = bellmanFord(dist, pred, source); cout << "Source Vertex: " << source<<endl; display(dist, pred); if(report) cout << "The graph has a negative edge cycle" << endl; else cout << "The graph has no negative edge cycle" << endl; }
আউটপুট
Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle