ค้นหาระยะทางที่สั้นที่สุดระหว่างโหนดที่ดีสองคู่ที่ต่างกันใน C++

สมมติว่าเรามีกราฟแบบไม่มีทิศทางที่ถ่วงน้ำหนักซึ่งมีโหนดต่างกัน N โหนดและขอบ M โหนดบางรายการเป็นโหนดที่ดี เราต้องหาระยะทางที่สั้นที่สุดระหว่างโหนดที่ดีสองโหนดที่ต่างกัน ในแผนภาพที่กำหนด สีเหลืองในกราฟต่อไปนี้ถือเป็นโหนดที่ดี

ดังนั้นหากอินพุตเป็นแบบ

ผลลัพธ์จะเป็น 11 เนื่องจากคู่ของโหนดที่ดีและระยะห่างระหว่างพวกเขาคือ:(1 ถึง 3) ระยะทางคือ 11, (3 ถึง 5) ระยะทางคือ 13, (1 ถึง 5) ระยะทางคือ 24, ออก โดยที่ 11 เป็นขั้นต่ำ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ไม่มี :=100005

• MAX_VAL :=99999999

• สร้างคิวลำดับความสำคัญหนึ่งคิว q

• ผลลัพธ์ :=MAX_VAL

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า good_verts[i] เป็นเท็จ −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • สำหรับการเริ่มต้น j :=1 เมื่อ j <=n อัปเดต (เพิ่ม j โดย 1) ทำ -

    • dist[j] :=MAX_VAL

    • กับ[j] :=0

  • dist[i] :=0

  • ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

    • ลบองค์ประกอบออกจาก q

  • แทรก { 0, i } ลงใน q

  • ดี :=0

  • ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

    • v :=องค์ประกอบด้านบนของ q

    • ลบองค์ประกอบออกจาก q

    • ถ้า vis[v] เป็นจริง ดังนั้น −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • กับ[v] :=1

    • ดี :=ดี + (1 เมื่อ good_verts[v] เป็นจริง มิฉะนั้น 0)

    • ถ้า dist[v]> ผลลัพธ์ แล้ว −

      • ออกจากวง

    • ถ้าดีเท่ากับ 2 และ good_verts[v] แล้ว −

      • ผลลัพธ์ :=ขั้นต่ำของผลลัพธ์และ dist[v]

      • ออกจากวง

    • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของกราฟ[v] อัปเดต (เพิ่ม j ทีละ 1) ให้ทำ -

      • ถึง :=graph[v, j].first

      • น้ำหนัก :=กราฟ[v, j].วินาที

      • ถ้า dist[v] + น้ำหนัก

        • dist[to] :=dist[v] + น้ำหนัก

        • แทรก { dist[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;

ผลลัพธ์

7