這個 C 程式透過移除任意 K 條邊來計算雙向加權圖中兩個給定節點之間的最短距離。它使用了修改過的 Dijkstra 演算法，將移除 K 條邊視為限制條件。該程式使用了一個優先隊列來有效地選擇節點，並根據移除的要求動態調整邊的權重。透過遍歷圖並找到最短路徑，它給出了給定節點之間的最小距離，並考慮了移除 K 條邊的影響。
步驟 1：建立一個結構來儲存節點及其與來源節點的分離距離
步驟2：將所有中心的分離度初始化為無限大，但來源中心的分離度設為0。
步驟3：將來源節點與其單獨的節點一起放入需求行中。
步驟4：重新執行下列步驟，直到需要的行被清除：
a. 從需要行中刪除具有最小移除的節點
b.對於出隊節點的每個相鄰節點，透過包含邊權重來計算未使用的刪除，並檢查它是否小於目前刪除。
c. 如果未使用的移除較少，則升級分離並將中心入隊到需求佇列中。
d.追蹤每個集線器的疏散邊緣的數量。
步驟5：在考慮移除K條邊之後，返回來源節點和目標節點之間最限制的路徑。
#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;
}
shortest distance: 8
步驟 1：用圖中邊的權重初始化一個二維網路 dist[][]。
步驟 2：初始化一個二維格子 evacuated[][]，用來追蹤每對節點之間被驅逐的邊的數量。
步驟 3：應用佛洛伊德-沃爾什計算方法，計算每個中繼站匹配之間的最短路徑，考慮撤離 K 條邊。
步驟4：在考慮排除K條邊之後，返回來源節點和目標節點之間最短的距離。
#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;
}
Shortest distance: 8
我們研究了兩種方法，透過考慮 K 條邊的疏散來找到雙向加權圖中給定中心之間最短的移除。這些方法，具體來說是改變迪傑斯特拉計算、佛洛伊德-沃歇爾計算，為理解問題提供了多種方法。透過利用C語言中的這些計算，我們將在滿足K條邊疏散的同時精確計算最小移除量。方法的選擇取決於圖表度量、複雜性以及當前問題的特定先決條件等組成部分。
以上是在雙向加權圖中，透過刪除任意K條邊，找到給定節點之間的最短距離的詳細內容。更多資訊請關注PHP中文網其他相關文章！
