Dijkstra এর সংক্ষিপ্ত পথ অ্যালগরিদম

প্রধান সমস্যাটি আগেরটির মতোই, প্রারম্ভিক নোড থেকে অন্য যে কোনও নোড পর্যন্ত, ক্ষুদ্রতম দূরত্বগুলি সন্ধান করুন৷ এই সমস্যায়, প্রধান পার্থক্য হল যে গ্রাফটি সংলগ্ন ম্যাট্রিক্স ব্যবহার করে উপস্থাপন করা হয়। (কস্ট ম্যাট্রিক্স এবং সংলগ্ন ম্যাট্রিক্স এই উদ্দেশ্যে একই রকম)।

সংলগ্ন তালিকা উপস্থাপনের জন্য, সময়ের জটিলতা হল O(V^2) যেখানে V হল G(V, E) গ্রাফে নোডের সংখ্যা।

ইনপুট এবং আউটপুট

ইনপুট:সংলগ্ন ম্যাট্রিক্স:আউটপুট:0 থেকে 1, ব্যবহার:0, খরচ:30 থেকে 2, ব্যবহার:1, খরচ:50 থেকে 3, ব্যবহার:1, খরচ:40 থেকে 4, ব্যবহার:3, খরচ:60 থেকে 5, ব্যবহার:2, খরচ:70 থেকে 6, ব্যবহার:4, খরচ:7

অ্যালগরিদম

dijkstraShortestPath(n, dist, next, start)

ইনপুট - নোডের মোট সংখ্যা, প্রতিটি শীর্ষের জন্য দূরত্বের তালিকা, পরবর্তী তালিকাটি সংরক্ষণ করার জন্য কোন নোডটি পরবর্তীতে আসে এবং বীজ বা শুরু শীর্ষবিন্দু।

আউটপুট - সূচনা থেকে অন্য সকল শীর্ষবিন্দুতে সংক্ষিপ্ততম পথ।

V do status[u] তে সকল শীর্ষবিন্দুর জন্য নির্বাচিত নোডের বর্তমান স্থিতি ধরে রাখতে একটি স্থিতি তালিকা তৈরি করা শুরু করুন [u] :=unconsidered dist[u] :=পরবর্তী খরচ ম্যাট্রিক্স ব্যবহার করে উৎস থেকে দূরত্ব [u] :=শুরু করুন সম্পন্ন স্থিতি[শুরু] :=বিবেচনা করা, dist[শুরু] :=0 এবং পরবর্তী [শুরু] :=φ যখন অবিবেচ্য শীর্ষবিন্দুকে গ্রহণ করুন কারণ দূরত্ব ন্যূনতম ডু স্ট্যাটাস [u] :=স্ট্যাটাস থাকলে V তে সমস্ত শীর্ষবিন্দুর জন্য বিবেচনা করা হয় [v] =অবিবেচ্য তারপর যদি dist[v]> dist[u] + খরচ[u,v] তারপর dist[v] :=dist[u] + cost[u,v] পরবর্তী[v] :=আপনি সম্পন্ন করা শেষ 

উদাহরণ

#include#define V 7#define INF 999using namespace std;// গ্রাফিন্ট costMat[V][V] ={ {0, 3, 6, INF, INF, INF, INF} এর খরচ ম্যাট্রিক্স , {3, 0, 2, 1, INF, INF, INF}, {6, 2, 0, 1, 4, 2, INF}, {INF, 1, 1, 0, 2, INF, 4}, { INF, INF, 4, 2, 0, 2, 1}, {INF, INF, 2, INF, 2, 0, 1}, {INF, INF, INF, 4, 1, 1, 0}}; সর্বনিম্ন (int *স্থিতি, int *dis, int n) { int i, min, index; min =INF; for(i =0; i -1) {স্থিতি[u] =2;//এখন বিবেচনা করা হয় (v =0; v dist[u] + costMat[u][v]) { dist[v] =dist[u] + costMat[u][v]; //আপডেট দূরত্ব পরবর্তী [v] ​​=u; } }} main() { int dis[V], next[V], i, start =0; dijkstra(V, dis, next, start); for(i =0; i 
আউটপুট
 <প্রে>0 থেকে 1, ব্যবহার:0, খরচ:30 থেকে 2, ব্যবহার:1, খরচ:50 থেকে 3, ব্যবহার:1, খরচ:40 থেকে 4, ব্যবহার:3, খরচ:60 থেকে 5, ব্যবহার:2 , খরচ:70 থেকে 6, ব্যবহার:4, খরচ:7