একক-উৎস সংক্ষিপ্ততম পথ, অঋণাত্মক ওজন

একক উৎস সংক্ষিপ্ত পথ অ্যালগরিদম (অ নেতিবাচক ওজনের জন্য) ডিজকস্ট্রা অ্যালগরিদম নামেও পরিচিত। একটি প্রদত্ত গ্রাফ G(V,E) এর সংলগ্ন ম্যাট্রিক্স উপস্থাপনা সহ রয়েছে এবং একটি উৎস শীর্ষবিন্দুও দেওয়া হয়েছে। ডিজকস্ট্রার অ্যালগরিদম গ্রাফ G এর অন্য কোনো শীর্ষ থেকে সোর্স শীর্ষবিন্দুর মধ্যে ন্যূনতম সংক্ষিপ্ততম পথ খুঁজে পেতে।

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

ইনপুট − সংলগ্ন ম্যাট্রিক্স −

আউটপুট −

অ্যালগরিদম

dijkstraShortestPath(n, dist, next, start)

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

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

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] :=আপনি সম্পন্ন করা শেষ 

উদাহরণ(C++)

#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){ status[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