C++ में दो अलग-अलग अच्छे नोड्स के किसी भी जोड़े के बीच सबसे कम दूरी ज्ञात करें

मान लीजिए कि हमारे पास एन अलग-अलग नोड्स और एम किनारों के साथ एक भारित अप्रत्यक्ष ग्राफ है, कुछ नोड्स अच्छे नोड्स हैं। हमें दो अलग-अलग अच्छे नोड्स के किसी भी जोड़े के बीच सबसे छोटी दूरी का पता लगाना है। दिए गए आरेख में निम्नलिखित ग्राफ में पीले रंग को अच्छा नोड माना जाता है।

तो, अगर इनपुट पसंद है

तो आउटपुट 11 होगा, क्योंकि अच्छे नोड्स के जोड़े और उनके बीच की दूरी है:(1 से 3) दूरी 11 है, (3 से 5) दूरी 13 है, (1 से 5) दूरी 24 है, बाहर जिनमें से 11 न्यूनतम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एन:=100005
MAX_VAL :=99999999
एक प्राथमिकता कतार बनाएं q
परिणाम:=MAX_VAL
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
- अगर good_verts[i] गलत है, तो -
  - निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
- इनिशियलाइज़ j :=1 के लिए, जब j <=n, अपडेट करें (j को 1 से बढ़ाएँ), करें -
  - जिला [जे] :=MAX_VAL
  - विज़ [जे]:=0
- जिला [i] :=0
- जबकि (नहीं q खाली है), करें -
  - q से तत्व हटाएं
- q में { 0, i } डालें
- अच्छा :=0
- जबकि (नहीं q खाली है), करें -
  - v:=q का शीर्ष तत्व
  - q से तत्व हटाएं
  - अगर vis[v] सत्य है, तो -
    - निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
  - विज़ [v] :=1
  - अच्छा :=अच्छा + (1 जब good_verts[v] सत्य है, अन्यथा 0)
  - अगर dist[v]> परिणाम, तो -
    - लूप से बाहर आएं
  - अगर अच्छा 2 और good_verts[v] के समान है, तो -
    - परिणाम :=न्यूनतम परिणाम और जिला[v]
    - लूप से बाहर आएं
  - इनिशियलाइज़ j :=0 के लिए, जब j <ग्राफ़ का आकार[v], अपडेट करें (1 से j बढ़ाएँ), करें -
    - से :=ग्राफ़[v, j].पहले
    - वजन:=ग्राफ[v, j].सेकंड
    - यदि जिला [v] + वजन <जिला [से], तो -
      - जिला [से]:=जिला [वी] + वजन
      - q में { dist[to], to } डालें q
वापसी परिणाम

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999
void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
   graph[x].push_back({ y, weight });
   graph[y].push_back({ x, weight });
}
int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
   priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
   int result = MAX_VAL;
   for (int i = 1; i <= n; i++) {
      if (!good_verts[i])
         continue;
      for (int j = 1; j <= n; j++) {
         dist[j] = MAX_VAL;
         vis[j] = 0;
      }
      dist[i] = 0;
      while (!q.empty())
      q.pop();
      q.push({ 0, i });
      int good = 0;
      while (!q.empty()) {
         int v = q.top().second;
         q.pop();
         if (vis[v])
         continue;
         vis[v] = 1;
         good += good_verts[v];
         if (dist[v] > result)
            break;
         if (good == 2 and good_verts[v]) {
            result = min(result, dist[v]);
            break;
         }
         for (int j = 0; j < graph[v].size(); j++) {
            int to = graph[v][j].first;
            int weight = graph[v][j].second;
            if (dist[v] + weight < dist[to]) {
               dist[to] = dist[v] + weight;
               q.push({ dist[to], to });
            }
         }
      }
   }
   return result;
}
int main() {
   int n = 5, m = 5;
   vector<pair<int, int> > graph[N];
   insert_edge(graph, 1, 2, 3);
   insert_edge(graph, 1, 2, 3);
   insert_edge(graph, 2, 3, 4);
   insert_edge(graph, 3, 4, 1);
   insert_edge(graph, 4, 5, 8);
   int k = 3;
   int good_verts[N], vis[N], dist[N];
   good_verts[1] = good_verts[3] = good_verts[5] = 1;
   cout << get_min_dist(graph, n, dist, vis, good_verts, k);
}

इनपुट

n = 5, m = 5
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 2, 3, 4);
insert_edge(graph, 3, 4, 1);
insert_edge(graph, 4, 5, 8);
k = 3
good_verts[1] = good_verts[3] = good_verts[5] = 1;