Dijkstra Algorithm  


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် တိကျသော Adobe က အမေဇုံ Cisco သည် အပြန်အလှန်ဖြေရှင်းချက်များ မော်ဂန်စတန်လေ Samsung Vizury
Dijkstra Algorithm သရုပ်ပြဇယား တပ်မက်သော အတိုဆုံးလမ်းကြောင်း သဘောတရား

Dijkstra သည် အတိုဆုံးလမ်းကြောင်း algorithm။ Dijkstra algorithm ကိုပေးထားသော start node မှ node အားလုံး၏အတိုဆုံးအကွာအဝေးကိုရှာဖွေသည်။ ၎င်းသည်အရင်းအမြစ် node တစ်ခုတည်းမှအတိုဆုံးလမ်းကြောင်းသစ်ပင်ကိုယုတ္တိနည်းအရဖန်တီးသည်။ ၎င်းသည်သစ်ပင်ရှိ node တစ်ခုချင်းစီသည်ပေးထားသော start node မှအနိမ့်ဆုံးအကွာအဝေးရှိသည့်နေရာတိုင်းတွင် node များကိုအမြဲတမ်းထည့်သွင်းခြင်းအားဖြင့်ဖြစ်သည်။

Dijkstra algorithm ကို တစ်ဦးဖြစ်ပါတယ် တပ်မက်သော အဆင့်တစ်ခုစီတွင် node တစ်ခုကိုရွေးချယ်ရန်အလွန်ရိုးရှင်းသောသင်္ချာအချက်ကိုအသုံးပြုသောချဉ်းကပ်မှု။

"အပြုသဘောဆောင်တဲ့ကိန်းဂဏန်းနှစ်ခုကိုထည့်တာကသွင်းအားစုနှစ်ခုလုံးထက်ပိုပြီးများတယ်။ "

algorithm  

ဤတွင် Dijkstra algorithm ကို

အသုံးပြုထားသော variable တွေကို

  1. nnode များအရေအတွက်။
  2. e: အနား၏အရေအတွက်။
  3. သွားရောက်ကြည့်ရှုသစ်ပင်ထဲတွင်ထည့်သွင်းထားသော node များကိုခြေရာခံရန်အရွယ်အစား n ခင်းကျင်းခြင်း။
  4. ပေးရi ၏ရောက်ရှိရန်အနည်းဆုံးကုန်ကျစရိတ်ကိုသိုလှောင်ရန်အရွယ်အစား n ခင်းကျင်းခြင်းth သစ်ပင်ရှိတရားဝင်လမ်းကြောင်းမှတဆင့် start node မှ node ။

ခြေလှမ်းများ

  1. Initialize သွားရောက်ကြည့်ရှုထားသောခင်းကျင်းမှုကို false ဖြင့်ဖော်ပြပါ၊ ၎င်းသည်လက်ရှိသစ်ပင်သည်အချည်းနှီးဖြစ်ကြောင်းပြသသည်။
  2. တန်ဖိုးကိုအကန့်အသတ်ဖြင့်စတင်ပါ။ ၎င်းသည်သစ်ပင်ရှိမှန်ကန်သောလမ်းကြောင်းမှတဆင့် start node မှမည်သည့် node ကိုမှမရောက်ရှိနိုင်ကြောင်းပြသသည်။
  3. start node သို့ရောက်ရှိရန်ကုန်ကျစရိတ်သည်အမြဲတမ်းသုညဖြစ်လိမ့်မည်။ ထို့ကြောင့် cost [start] = 0 ဖြစ်သည်။
  4. ယခုကြားဖြတ်တိုင်းတွင်သစ်ပင်ထဲတွင်ထည့်ရန် node တစ်ခုကိုရွေးချယ်လိုက်သည်။ ဤကြောင့်သစ်ပင်ထဲတွင် n node များထည့်ရန် n ကြားမှာလိုအပ်သည်။
    • အနိမ့်ဆုံးကုန်ကျစရိတ်ရှိပြီးလက်ရှိလတ်တလောလည်ပတ်မှုမရှိသောဆိုလိုသည်မှာသစ်ပင်ထဲတွင်မရှိသော node တစ်ခုကိုရွေးချယ်ပါ။
    • အသစ်ထည့်သွင်းထားသော node နှင့်ကပ်လျက်ဖြစ်သော non-visit node များကုန်ကျစရိတ်ကိုယခင်နှင့်လမ်းကြောင်းအသစ်အားအနည်းဆုံးနှင့်အသစ်ပြောင်းပါ။
    • လည်ပတ်ခဲ့အဖြစ် node ကိုမှတ်သားပါ။
လည်းကြည့်ရှုပါ
ဟနွိုင်းမျှော်စင်

Dijkstra Algorithm ၏ဥပမာ  

ဂရပ်တစ်ခုပေးထားပြီး A မှ node အားလုံး၏အနိမ့်ဆုံးအကွာအဝေးကို start node တစ်ခုအဖြစ်တွက်ချက်ပါ။

dijkstra algorithmတွယ်အပ်

Dijkstra Algorithm ကိုအဆင့်ဆင့်ဖြေရှင်းခြင်း

dijkstra algorithmတွယ်အပ်
တစ် ဦး ထံမှ A ၏ 1. အကွာအဝေး 0 ဖြစ်ပါတယ်

 

dijkstra algorithmတွယ်အပ်
တစ် ဦး ကနေ C ၏ 2. အကွာအဝေး 1 ဖြစ်ပါတယ်

 

dijkstra algorithmတွယ်အပ်
တစ် ဦး ကနေ: D ၏ 3. အကွာအဝေး 3 ဖြစ်ပါတယ်

 

တွယ်အပ်
တစ် ဦး ထံမှ B က၏ 4. အကွာအဝေး 3 ဖြစ်ပါတယ်

 

တွယ်အပ်
A ကနေ E ၏ 5. အကွာအဝေး 7 ဖြစ်ပါတယ်

Dijkstra Algorithm ၏အားနည်းချက်  

ကျွန်ုပ်တို့သိသည်နှင့်အမျှ Dijkstra တွင်အသုံးပြုသောအခြေခံပစ္စည်းသည်အပေါင်းဂဏန်းနှစ်လုံးထပ်ပေါင်းခြင်းဖြစ်သည်။ ဤသည်သည်ဤ algorithm သည်အနုတ်လက္ခဏာများပါဝင်သောဂရပ်၏အမှု၌မှားယွင်းသောအဖြေကိုဖြစ်ပေါ်စေနိုင်သည်။

နမူနာ  

ဂရပ်ကိုကြည့်ပါ

တွယ်အပ်

node စတင်ခြင်း: တစ်ဦးက

Dijkstra သည်အေမှ B သို့ရောက်ရှိရန်အနည်းဆုံးအကွာအဝေးအဖြစ်တွက်ချက်သည်။

သို့သော် A-> C-> E-> B လမ်းကြောင်းသည် ၂ မှကုန်ကျမည့်အေမှ B သို့ရောက်ရှိရန်ရှင်းရှင်းလင်းလင်းတွေ့မြင်နိုင်သည်။

Dijkstra Algorithm အပေါ်မေးခွန်း  

n node များနှင့် e edges များပါ ၀ င်သောညွှန်ကြားထားသည့်တွက်ချက်မှုဂရပ်တစ်ခုအား ပေး၍ သင်၏လုပ်ငန်းသည်ပေးထားသော start node မှ node တစ်ခုစီသို့ရောက်ရှိရန်အနည်းဆုံးကုန်ကျစရိတ်ကိုရှာဖွေရန်ဖြစ်သည်။  

input

ထည့်သွင်းမှု၏ပထမ ဦး ဆုံးလိုင်းတွင်ကိန်းပြည့်နှစ်ခု (အနား၏နံပါတ်) နှင့်အီး (အနား၏နံပါတ်) ပါ ၀ င်သည်။

နောက်လာမည့်အီးလိုင်းများတွင် u, v နှင့် w ကိန်းဂဏန်းများကိုခွဲထားသောကိန်းဂဏန်းများပါရှိရာ

  • u: အရင်းအမြစ် node ကို
  • v: ဦး တည်ရာ node ကို
  • w: အစွန်း၏အလေးချိန်

နောက်ဆုံးလိုင်းတွင် s n ပါဝင်ပြီး start node ကိုဆိုလိုသည်

ကန့်သတ်ချက်များ

1 <= n <= 1000

0 င် <= အီး <= (* * (--1)) / 2

1 <= အလေးချိန် <= 103

ဂရပ်တွင် Self-loop နှင့်အနားများစွာမပါပါ။

Dijkstra Algorithm အတွက် C ++ Code  

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;

// Function to find the non-visited node which is at minimum distance
int findMin(int n,int cost[],bool visited[]){
    int min=INF;
    int node=0;
    for(int i=0;i<n;i++){
        if(visited[i]==false && min>cost[i]){
            min=cost[i];
            node=i;
        }
    }
    return node;
}
void dijkstra(int n, vector<pair<int,int>> graph[], int start){
    bool visited[n];    // to specify which nodes are yet to visit
    int cost[n];            // cost[i] specifies the minimum cost to reach ith node from start node through visited nodes
    for(int i=0;i<n;i++){
        cost[i]=INF;                          // initialize cost array with INFINITY
                                             // to signify that all nodes are non-reachable initially
        visited[i]=false;                     // initialize visited array with false 
                                             // to signify that all nodes are non-visited initially
    }
    
    cost[start]=0;                           // minimum cost to reach the start node will be zero
    int count=0;                             // count will keep track of how many nodes are visited till now
    
    while(count<n){
        int node = findMin(n,cost,visited);
        visited[node]=true;
        for(auto &i:graph[node]){
            if(visited[i.first]==false){
                cost[i.first]=min(cost[i.first],cost[node]+(i.second));
            }
        }
        count++;
    }
    
    for(int i=0;i<n;i++){
        cout<<"Distance of node "<<i<<" from node "<<start<<" is "<<cost[i]<<"\n";
    }
}
int main(){
    int n,e;
    cin>>n>>e;
    vector<pair<int,int>> graph[n];
    for(int i=0;i<e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(make_pair(v,w));
        graph[v].push_back(make_pair(u,w));
    }
    int start;
    cin>>start;
    dijkstra(n,graph,start);
}
5 7
0 2 5
0 1 3
2 3 2
3 4 5
2 4 1
4 1 4
2 3 7
0
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 3
Distance of node 2 from node 0 is 5
Distance of node 3 from node 0 is 7
Distance of node 4 from node 0 is 6

Dijkstra Algorithm အတွက် Java Code  

import java.util.Scanner;


public class Main {
  public static int [][] graph;
  public static int [] visited;
  public static int [] cost;
  public static int start;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n,e, INF = Integer.MAX_VALUE;
      n = sc.nextInt();
      e = sc.nextInt();
      
      graph = new int [n][n];
      visited = new int [n];
      cost = new int[n];
        
      for (int i = 0; i < n; i++) {			
        for (int j = 0; j < n; j++) {
          graph[i][j] = -1;
        }
      }
      
      for (int i = 0; i < e; i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        int w = sc.nextInt();
        graph[u][v] = w;
        graph[v][u] = w;
      }
      
      start = sc.nextInt();
      
      for (int i = 0; i < n; i++) {
        cost[i]=INF;
      }
      cost[start]=0;
      
      dijkstra(start);
      printResult();
    }
  
  /* Recursive function to find the minimum distance of each node from given start node*/
  public static void dijkstra(int start){
    for (int i = 0; i <cost.length; i++) {
      if (graph[start][i] > -1 && cost[i] > (graph[start][i] + cost[start]) ){
        cost[i] = graph[start][i] + cost[start];
      }
    }
    
    int j = minDist();
    if (j  == -1 )
      return;
    
    visited[j] = 1;
    dijkstra(j);		
  }
  
  /* Function to print the distance of each node from given start node*/
  public static void printResult(){
    for (int i = 0; i <cost.length; i++) {
    		System.out.println("Distance of node "+i+" from node "+start+" is "+cost[i]);
    }
  }
  
  /* Function to find non-visited node with minimum distance*/
  public static int minDist(){
    int minDistance = Integer.MAX_VALUE;
    int index = -1; 
    for (int i=0; i<cost.length; i++){
      if (minDistance>cost[i] && visited[i] == 0){
        minDistance = cost[i];
        index = i;				
      }
    }
    return index;
  }

}
Input:
4 5
0 1 12
0 3 24
2 0 3
1 3 10
3 2 12
0
Output:
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 12
Distance of node 2 from node 0 is 3
Distance of node 3 from node 0 is 15

အချိန်ရှုပ်ထွေးမှု: အို (n * n)

နိမ့်ဆုံးကုန်ကျစရိတ်နှင့် node ကိုရွေးချယ်ရန် Dijkstra algorithm ၏အချိန်ရှုပ်ထွေးမှု binary heap ကို အသုံးပြု၍ တိုးတက်နိုင်သည် (အဆင့် ၄)

လည်းကြည့်ရှုပါ
Array of Pairs of ပေးထားသော၎င်းတွင်ရှိရှိသမျှ Symmetric Pairs ကိုရှာပါ

အညွှန်း

ပိုပြီးဖြတ်သန်းသွားပါ အင်တာဗျူးမေးခွန်းများကို