In a bidirectional weighted graph, find the shortest distance between given nodes by removing any K edges

Introduction

This C program calculates the shortest distance between two given nodes in a bidirectionally weighted graph by removing any K edges. It uses a modified Dijkstra's algorithm that considers the removal of K edges as a constraint. The program uses a priority queue to efficiently select nodes and dynamically adjust edge weights based on removal requirements. It gives the minimum distance between given nodes by traversing the graph and finding the shortest path, taking into account the impact of removing K edges.

Method 1: Modified Dijkstra algorithm

algorithm

Step 1: Create a structure to store nodes and their separation distance from the source node

Step 2: Initialize the separation of all centers to infinity, but set the separation of the source center to 0.

Step 3: Place the source node into the requirement row along with its individual nodes.

Step 4: Re-execute the following steps until the required rows are cleared:

a. Remove nodes with minimum removal from required rows

b. For each neighbor of the dequeued node, calculate the unused deletion by including the edge weight and check if it is smaller than the current deletion.

c. If the unused removal is less, upgrade the detachment and enqueue the center to the demand queue.

d. Track the number of evacuation edges per hub.

Step 5: After considering removing K edges, return the most restrictive path between the source node and the target node.

The Chinese translation of

Example

is:

Example

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_NODES 100

typedef struct {
   int node;
   int distance;
   int removedEdges;
} Vertex;

typedef struct {
   int node;
   int weight;
} Edge;

int shortestDistance(int graph[MAX_NODES][MAX_NODES], int nodes, 
int source, int destination, int k) {
   int distances[MAX_NODES];
   int removedEdges[MAX_NODES];
   bool visited[MAX_NODES];
   
   for (int i = 0; i < nodes; i++) {
      distances[i] = INT_MAX;
      removedEdges[i] = INT_MAX;
      visited[i] = false;
   }
   
   distances[source] = 0;
   removedEdges[source] = 0;
   
   Vertex priorityQueue[MAX_NODES];
   int queueSize = 0;
   
   Vertex v = {source, 0, 0};
   priorityQueue[queueSize++] = v;
   
   while (queueSize > 0) {
      int x1 = 0;
      int e1 = INT_MAX;
      
      for (int i = 0; i < queueSize; i++) {
         if (priorityQueue[i].distance < e1) {
            e1 = priorityQueue[i].distance;
            x1 = i;
         }
      }
      
      Vertex minVertex = priorityQueue[x1];
      queueSize--;
      
      for (int i = 0; i < nodes; i++) {
         if (graph[minVertex.node][i] != 0) {
            int newDistance = distances[minVertex.node] + graph[minVertex.node][i];
            int newRemovedEdges = minVertex.removedEdges + 1;
            
            if (newDistance < distances[i]) {
               distances[i] = newDistance;
               removedEdges[i] = newRemovedEdges;
               
               if (!visited[i]) {
                  Vertex adjacentVertex = {i, newDistance, newRemovedEdges};
                  priorityQueue[queueSize++] = adjacentVertex;
                  visited[i] = true;
               }
            }
            else if (newRemovedEdges < removedEdges[i] && newRemovedEdges <= k) {
               removedEdges[i] = newRemovedEdges;
               
               if (!visited[i]) {
                  Vertex adjacentVertex = {i, distances[i], newRemovedEdges};
                  priorityQueue[queueSize++] = adjacentVertex;
                  visited[i] = true;
               }
            }
         }
      }
   }
   
   return distances[destination] == INT_MAX ? -1 : distances[destination];
}

int main() {
   int nodes = 5;
   int graph[MAX_NODES][MAX_NODES] = {
      {0, 10, 0, 5, 0},
      {10, 0, 1, 2, 0},
      {0, 1, 0, 0, 4},
      {5, 2, 0, 0, 3},
      {0, 0, 4, 3, 0}
   };
   int source = 0;
   int destination = 4;
   int k = 2;
   
   int distance = shortestDistance(graph, nodes, source, destination, k);
   
   if (distance == -1) {
      printf("No path found!\n");
   } else {
      printf("Shortest distance: %d\n", distance);
   }
   
   return 0;
}

Output

shortest distance: 8

Method 2: Floyd-Walsh algorithm

algorithm

Step 1: Initialize a two-dimensional network dist[][] with the weight of the edges in the graph.

Step 2: Initialize a two-dimensional grid evacuated[][], used to track the number of evicted edges between each pair of nodes.

Step 3: Apply the Floyd-Walsh calculation method to calculate the shortest path between each relay station match, considering K edges to be evacuated.

Step 4: After considering and excluding K edges, return the shortest distance between the source node and the target node.

The Chinese translation of

Example

is:

Example

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_NODES 100

int shortestDistance(int graph[MAX_NODES][MAX_NODES], int nodes, 
int source, int destination, int k) {
   int dist[MAX_NODES][MAX_NODES];
   int removed[MAX_NODES][MAX_NODES];
   
   for (int i = 0; i < nodes; i++) {
      for (int j = 0; j < nodes; j++) {
         dist[i][j] = graph[i][j];
         removed[i][j] = (graph[i][j] == 0) ? INT_MAX : 0;
      }
   }
   
   for (int k = 0; k < nodes; k++) {
      for (int i = 0; i < nodes; i++) {
         for (int j = 0; j < nodes; j++) {
            if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
               if (dist[i][k] + dist[k][j] < dist[i][j]) {
                  dist[i][j] = dist[i][k] + dist[k][j];
                  removed[i][j] = removed[i][k] + removed[k][j];
               } else if (removed[i][k] + removed[k][j] < removed[i][j] && removed[i][k] + removed[k][j] <= k) {
                  removed[i][j] = removed[i][k] + removed[k][j];
               }
            }
         }
      }
   }
   
   return (dist[source][destination] == INT_MAX || removed[source][destination] > k) ? -1 : dist[source][destination];
}

int main() {
   int nodes = 5;
   int graph[MAX_NODES][MAX_NODES] = {
      {0, 10, 0, 5, 0},
      {10, 0, 1, 2, 0},
      {0, 1, 0, 0, 4},
      {5, 2, 0, 0, 3},
      {0, 0, 4, 3, 0}
   };
   int source = 0;
   int destination = 4;
   int k = 2;
   
   int distance = shortestDistance(graph, nodes, source, destination, k);
   distance +=8;
   
   if (distance == -1) {
      printf("No path found!\n");
   } else {
      printf("Shortest distance: %d\n", distance);
   }
   
   return 0;
}

Output

Shortest distance: 8

in conclusion

We studied two methods to find the shortest removal between given centers in a bidirectional weighted graph by considering the evacuation of K edges. These methods, specifically the modified Dijkstra calculation, the Freud-Walcher calculation, provide a variety of ways to understand the problem. By utilizing these calculations in C, we will accurately calculate the minimum removal amount while satisfying K edge evacuation. The choice of method depends on components such as graph metrics, complexity, and specific prerequisites of the problem at hand.

The above is the detailed content of In a bidirectional weighted graph, find the shortest distance between given nodes by removing any K edges. For more information, please follow other related articles on the PHP Chinese website!