algorithm
डीजकस्ट्रा का एल्गोरिथम

दिज्क्स्ट्रा का सबसे छोटा पथ एल्गोरिथम

आगे बढ़ने से पहले, आसन्न मैट्रिक्स और बीएफएस के बारे में एक संक्षिप्त विचार रखने की सिफारिश की जाती है

दिज्क्स्ट्रा के एल्गोरिथ्म को एकल-स्रोत लघु पथ एल्गोरिथ्म के रूप में जाना जाता है। यह एक ग्राफ में नोड्स के बीच सबसे छोटे रास्तों को खोजने के लिए उपयोग किया जाता है, जो उदाहरण के लिए, सड़क नेटवर्क का प्रतिनिधित्व कर सकता है। इसकी कल्पना 1956 में एग्जर डब्ल्यू। डिक्स्ट्रा ने की थी और तीन साल बाद प्रकाशित की।

हम चौड़ाई पहले खोज (बीएफएस) खोज एल्गोरिथ्म का उपयोग करके सबसे छोटा रास्ता पा सकते हैं। यह एल्गोरिथ्म ठीक काम करता है, लेकिन समस्या यह है कि, यह मानता है कि प्रत्येक पथ के ट्रैवर्सिंग की लागत समान है, अर्थात प्रत्येक किनारे की लागत समान है। दिज्क्स्ट्रा का एल्गोरिथ्म हमें सबसे छोटा रास्ता खोजने में मदद करता है जहां प्रत्येक पथ की लागत समान नहीं है।

सबसे पहले हम देखेंगे, बीजेएस को डायजेस्ट्रा के एल्गोरिथ्म को लिखने के लिए कैसे संशोधित किया जाए, फिर हम इसे पूर्ण दिक्जस्ट्रा के एल्गोरिदम बनाने के लिए प्राथमिकता कतार जोड़ेंगे।

मान लीजिए, स्रोत से प्रत्येक नोड की दूरी d [] सरणी में रखी गई है। जैसा कि, d [3] दर्शाता है कि d [3] समय स्रोत से नोड 3 तक पहुंचने के लिए लिया गया है। यदि हम दूरी नहीं जानते हैं, तो हम d [3] में अनंतता को संचित करेंगे। इसके अलावा, लागत [यू] [v] यूवी की लागत का प्रतिनिधित्व करते हैं। इसका मतलब है कि यह यू नोड से वी नोड तक जाने के लिए लागत [यू] [वी] लेता है।

हमें एज रिलैक्सेशन को समझने की जरूरत है। मान लीजिए, आपके घर से, जो स्रोत है , ए को जगह पर जाने के लिए 10 मिनट लगते हैं। और B को जगह जाने में 25 मिनट लगते हैं। हमारे पास है,

d[A] = 10
d[B] = 25

अब कहते हैं कि A को जगह B से जाने में 7 मिनट लगते हैं, इसका मतलब है कि:

cost[A][B] = 7

फिर हम जगह बी को स्रोत से स्रोत से एक जगह पर जाकर तो जगह एक से जाने के लिए और, जगह बी, जो 10 + 7 = 17 मिनट, बजाय 25 मिनट का समय लगेगा करने के लिए जा सकते हैं। इसलिए,

d[A] + cost[A][B] < d[B]

फिर हम अपडेट करते हैं,

d[B] = d[A] + cost[A][B]

इसे विश्राम कहते हैं। हम नोड यू से नोड v पर जाएंगे और यदि d [u] + लागत [u] [v] <d [v] तो हम d [v] = d [u] + लागत [u] [v] को अपडेट करेंगे।

BFS में, हमें दो बार किसी भी नोड पर जाने की आवश्यकता नहीं थी। हमने केवल यह जाँच की है कि नोड का दौरा किया गया है या नहीं। यदि यह दौरा नहीं किया गया था, तो हमने नोड को कतार में धकेल दिया, इसे विज़िट के रूप में चिह्नित किया और 1. द्वारा दूरी में वृद्धि की। डायजेक्स्ट्रा में, हम एक नोड को कतार में धकेल सकते हैं और इसे विज़िट के साथ अपडेट करने के बजाय, हम आराम करते हैं या नए किनारे को अपडेट करते हैं। आइए एक उदाहरण देखें:

मान लेते हैं, नोड 1 स्रोत है । फिर,

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

हम सेट करते हैं, डी [2], डी [3] और डी [4] अनंत तक क्योंकि हम अभी तक दूरी नहीं जानते हैं। और स्रोत की दूरी निश्चित रूप से 0 है । अब, हम स्रोत से अन्य नोड्स पर जाते हैं और यदि हम उन्हें अपडेट कर सकते हैं, तो हम उन्हें कतार में धकेल देंगे। उदाहरण के लिए कहें, हम बढ़त 1-2 से पार करेंगे। जैसा कि d [1] + 2 <d [2] जो d [2] = 2 करेगा । इसी तरह, हम किनारे पर 1-3 पार करेंगे जो d [3] = 5 बनाता है।

हम स्पष्ट रूप से देख सकते हैं कि 5 सबसे छोटी दूरी नहीं है जिसे हम नोड 3 पर जाने के लिए पार कर सकते हैं। तो केवल एक बार BFS की तरह एक नोड का पता लगाना यहाँ काम नहीं करता है। यदि हम धार 2-3 का उपयोग करके नोड 2 से नोड 3 तक जाते हैं , तो हम d [3] = d [2] + 1 = 3 को अपडेट कर सकते हैं। इसलिए हम देख सकते हैं कि एक नोड को कई बार अपडेट किया जा सकता है। कितनी बार पूछते हो? एक नोड को अपडेट किए जाने की अधिकतम संख्या एक नोड के इन-डिग्री की संख्या है।

आइए कई बार किसी भी नोड पर जाने के लिए छद्म कोड देखें। हम केवल BFS को संशोधित करेंगे:

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

इसका उपयोग स्रोत से सभी नोड का सबसे छोटा रास्ता खोजने के लिए किया जा सकता है। इस कोड की जटिलता इतनी अच्छी नहीं है। यहाँ पर क्यों,

बीएफएस में, जब हम नोड 1 से अन्य सभी नोड्स पर जाते हैं, तो हम पहले आओ, पहले पाओ की विधि का पालन करते हैं । उदाहरण के लिए, हम नोड 2 प्रक्रिया से पहले स्रोत से नोड 3 के पास गया। यदि हम स्रोत से नोड 3 पर जाते हैं, तो हम नोड 4 को 5 + 3 = 8 के रूप में अपडेट करते हैं। जब हम फिर से नोड 3 को नोड 2 से अपडेट करते हैं, तो हमें नोड 4 को 3 + 3 = 6 के रूप में फिर से अपडेट करना होगा! इसलिए नोड 4 को दो बार अपडेट किया जाता है।

दिज्क्स्त्र ने प्रस्तावित किया, पहले आओ, पहले पाओ की विधि के बजाय, यदि हम निकटतम नोड्स को पहले अपडेट करते हैं, तो यह कम अपडेट करेगा। अगर हम नोड 2 को पहले संसाधित करते हैं, तो नोड 3 को पहले अपडेट किया गया होगा, और नोड 4 को अपडेट करने के बाद, हम आसानी से कम से कम दूरी प्राप्त करेंगे! विचार कतार से चुनना है, नोड, जो स्रोत के सबसे करीब है। इसलिए हम यहां पर प्राथमिकता कतार का उपयोग करेंगे ताकि जब हम कतार को पॉप करें, तो यह हमें स्रोत से निकटतम नोड यू लाएगा। यह कैसे होगा? यह इसके साथ d [u] के मूल्य की जांच करेगा।

आइए देखें छद्म कोड:

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

छद्म कोड स्रोत से अन्य सभी नोड्स की दूरी देता है। यदि हम किसी एकल नोड v की दूरी जानना चाहते हैं, तो हम केवल उस मूल्य को वापस कर सकते हैं जब v कतार से पॉप किया जाता है।

अब, दिज्क्स्ट्रा का एल्गोरिदम काम करता है जब एक नकारात्मक बढ़त है? यदि कोई नकारात्मक चक्र है, तो अनंत लूप होगा, क्योंकि यह हर बार लागत को कम करता रहेगा। यहां तक कि अगर एक नकारात्मक बढ़त है, तो दिक्जस्त्र काम नहीं करेगा, जब तक कि हम लक्ष्य के ठीक बाद वापस नहीं आते। लेकिन फिर, यह एक दिक्जस्ट्रा एल्गोरिथ्म नहीं होगा। हमें नकारात्मक बढ़त / चक्र के प्रसंस्करण के लिए बेलमैन-फोर्ड एल्गोरिथ्म की आवश्यकता होगी।

जटिलता:

बीएफएस की जटिलता हे (लॉग (वी + ई)) जहां वी नोड्स की संख्या है और ई किनारों की संख्या है। दिज्क्स्त्र के लिए, जटिलता समान है, लेकिन प्राथमिकता कतार की छँटाई में O (logV) लगता है । तो कुल जटिलता है: O (Vlog (V) + E)

नीचे दिए गए जावा मैट्रिक्स का उदाहरण है, एडजेंसी मैट्रिक्स का उपयोग करते हुए डीजेकस्ट्रा के सबसे छोटे पथ एल्गोरिथम को हल करने के लिए

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    void dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

कार्यक्रम का अपेक्षित आउटपुट है

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14