ফ্লয়েড ওয়ারশ্যালের অ্যালগরিদম

কম্পিউটার বিজ্ঞান এ, ফ্লয়েড – ওয়ারশাল অ্যালগরিদম (ফ্লয়েডের অ্যালগরিদম, রয়-ওয়ারশাল অ্যালগরিদম, রায়-ফ্লয়েড অ্যালগরিদম বা ডাব্লুএফআইআই অ্যালগরিদম নামেও পরিচিত) হ'ল ধনাত্মক বা নেতিবাচক প্রান্তের ওজনযুক্ত গ্রাফের মধ্যে সংক্ষিপ্ততম পথগুলি খুঁজে পাওয়ার জন্য একটি অ্যালগরিদম (তবে কোনও নেতিবাচক চক্র ব্যতীত)।^[১][২] অ্যালগরিদমের একক সম্পাদনা সমস্ত জোড়ের কোণের মধ্যে সংক্ষিপ্ততম পথের দৈর্ঘ্য (সংযুক্ত ওজন) পাবে। যদিও এগুলি নিজেই পথের বিশদটি ফেরত দেয় না, তবে অ্যালগরিদমের সাধারণ পরিবর্তনগুলি সহ পথগুলি পুনর্গঠন করা সম্ভব। অ্যালগরিদমের সংস্করণগুলি কোনও সম্পর্কের ট্রানজিটিভ ক্লোজার সন্ধান করতেও ব্যবহার করা যেতে পারে।

ইতিহাস ও নামকরণ

ফ্লয়েড – ওয়ারশাল অ্যালগরিদম গতিশীল প্রোগ্রামিংয়ের একটি উদাহরণ এবং এটি ১৯৬২ সালে রবার্ট ফ্লয়েড দ্বারা বর্তমানে প্রকাশিত হয়েছিল।^[৩] এটি মূলত ১৯৫৯ সালে বার্নার্ড রায়^[৪] এবং ১৯৬২ সালে স্টিফেন ওয়ারশালের^[৫] দ্বারা প্রকাশিত অ্যালগরিদমের মতোই। এটি ক্লিনির অ্যালগরিদম (১৯৫৬ সালে প্রকাশিত)^[৬] সাথে একটি নিয়মিত অভিব্যক্তিতে সীমাবদ্ধ অটোমেটনকে নিয়মিত অভিব্যক্তিতে রূপান্তরিত করার জন্যও ব্যবহার করা হয়। তিন নেস্টেড লুপ হিসাবে আলগোরিদিম আধুনিক সূচনাটি প্রথম প্রকাশিত হয়েছিল পিটার ইনগারম্যান, ১৯৬২ সালে।^[৭]

অ্যালগরিদম

অ্যালগরিদমের মূল ধারণাটি হ'ল যে কোনও দুটি শীর্ষবিন্দু মধ্যে বেশ কয়েকটি সংখ্যক ইনক্রিমেন্টাল পর্যায়ে সবচেয়ে সংক্ষিপ্ত পথ সন্ধানের প্রক্রিয়াটিকে বিভাজন করা। ধরে নাও একটি পুনর্নির্দেশিত ওজনযুক্ত গ্রাফ G, যার মধ্যে n খানা শীর্ষবিন্দু রয়েছে। এই গ্রাফ G এর জন্য একটি অপেক্ষক d[i][j] ধরে নেয়া হলো যার মধ্যে যে কোনো দুই শীর্ষবিন্দু i ও j এর সংক্ষিপ্ততম পথগুলি সংরক্ষণ করা হবে। 

প্রাথমিকভাবে, আমরা d[i][j] = ${\displaystyle w_{i,j}}$ দিয়ে ম্যাট্রিক্স পূরণ করতে পারি যদি i এবং j শীর্ষবিন্দুর মধ্যে ${\displaystyle w_{i,j}}$ ওজনের একটি প্রান্ত থাকে। তবে যদি i ও j এর মধ্যে কোনো প্রান্ত না থাকে তবে d[i][j] = ∞  ধরা হবে। যদিও কার্যকরীভাবে কিছু উচ্চ মান ধরা হয। এবার আমরা প্রত্যেক k-তম ধাপে আমরা (i, j) শীর্ষকোণগুলির দূরত্বগুলো গণনা করে ম্যাট্রিক্স d[i][j] তে সংরক্ষণ করবো। এই গণনা করার জন্যে দুটি মৌলিকভাবে পৃথক কেস রয়েছে:

1. k -তম ধাপে শীর্ষবিন্দু i থেকে শীর্ষবিন্দু j সবচেয়ে সংক্ষিপ্ত পথটি (k -১)-তম ধাপের সঙ্গে সমান। এই কেসে d[i][j] এর মান পরিবর্তন হবে না। 
2. k -তম ধাপে শীর্ষবিন্দু i থেকে শীর্ষবিন্দু j পথটি সবচেয়ে সংক্ষিপ্ত। এই কেসে d[i][j] এর মান পরিবর্তন হবে।

এই দুটি কেসের সংমিশ্রণে আমরা দেখতে পেলাম যে আমরা সমস্ত শীর্ষবিন্দু জোড়া (i ,j) এর দৈর্ঘ্য গণনা করার k-তম ধাপে নিম্নলিখিত ভাবে করতে পারি : 

d_k[i][j] = ${\displaystyle \min(}$ d_k-1[i][j], d_k-1[i][k] + d_k-1[k][j] )

ফ্লয়েড ওয়ারশ্যালের অ্যালগরিদমের C++ কোড নিম্নরূপ:

vector<vector<int>> floydWarshall (vector<vector<int>> &graph)  
{  
    /* vector<vector<int>> graph  হলো অন্তিক ম্যাট্রিক্স।
    এই অন্তিক ম্যাট্রিক্স এ প্রত্যেক শীর্ষবিন্দু জোড়ার  ওজন 
    সংরক্ষণ করা আছে। ্রিক্স */
    
    int i, j, k;
    int n=graph.size();//শীর্ষবিন্দুর সংখ্যা
    
    /* vector<vector<int>> dist এই ম্যাট্রিক্স এ 
     অবশেষে প্রতিটি শীর্ষবিন্দু জোড়ার  
    সংক্ষিপ্ততম পথটির দূরত্ব সংরক্ষণ 
    করা  থাকবে।*/
    vector<vector<int>> dist(n,vector<int> (n,INT_MAX));
    
    /*প্রাথমিকভাবে সমস্ত প্রান্তের মানগুলি
    dist ম্যাট্রিক্সে সংরক্ষণ ক রা হচ্ছে
    */
    for (i = 0; i < n; i++)  
        for (j = 0; j < n; j++)  
            dist[i][j] = graph[i][j];  
  
    /* ফ্লয়েড-ওয়ারশল অ্যালগোরিদম */
    for (k = 0; k < n; k++)  
    {  
        for (i = 0; i < n; i++)  
        { 
            for (j = 0; j < n; j++)  
            {  
                if (dist[i][k] + dist[k][j] < dist[i][j])  
                    dist[i][j] = dist[i][k] + dist[k][j];  
            }  
        }  
    }  
  
    return dist;  
}

উদাহরণ

উপরের অ্যালগরিদমটি নিচের ছবিতে ব্যবহার করা হয়েছে :

K এর প্রতিটি পুনরাবৃত্তির দূরত্বের ম্যাট্রিক্সটি হবে:

পুনরাবৃত্তি ১

k = 0		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

পুনরাবৃত্তি ২

k = 1		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

পুনরাবৃত্তি ৩

k = 2		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

পুনরাবৃত্তি ৪

k = 3		j
		1	2	3	4
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0

পুনরাবৃত্তি ৫

k = 4		j
		1	2	3	4
i	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

বিশ্লেষণ

এই অ্যালগরিদমের জন্য:

গড় সময়ের জটিলতা = ${\displaystyle \Theta (n^{3})}$

এবং,

খারাপ স্থান জটিলতা = ${\displaystyle O(n^{2})}$

তথ্যসূত্র

1. টেমপ্লেট:Introduction to Algorithms See in particular Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565 and Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
2. Kenneth H. Rosen (২০০৩)। Discrete Mathematics and Its Applications, 5th Edition। Addison Wesley। আইএসবিএন 978-0-07-119881-3। 
3. Floyd, Robert W. (জুন ১৯৬২)। "Algorithm 97: Shortest Path"। Communications of the ACM। 5 (6): 345। ডিওআই:10.1145/367766.368168। 
4. Roy, Bernard (১৯৫৯)। "Transitivité et connexité."। C. R. Acad. Sci. Paris (French ভাষায়)। 249: 216–218। উদ্ধৃতি শৈলী রক্ষণাবেক্ষণ: অচেনা ভাষা (link)
5. Warshall, Stephen (জানুয়ারি ১৯৬২)। "A theorem on Boolean matrices"। Journal of the ACM। 9 (1): 11–12। ডিওআই:10.1145/321105.321107। 
6. Kleene, S. C. (১৯৫৬)। "Representation of events in nerve nets and finite automata"। C. E. Shannon and J. McCarthy। Automata Studies। Princeton University Press। পৃষ্ঠা 3–42। 
7. Ingerman, Peter Z. (নভেম্বর ১৯৬২)। "Algorithm 141: Path Matrix"। Communications of the ACM। 5 (11): 556। ডিওআই:10.1145/368996.369016।