在具有特殊边权重的图中努力计算最短路径

Question

我一直在研究一个问题，我需要在考虑两种类型的边权重的情况下找到图中的最短路径：正常和特殊。 在此处检查问题。

我构建了一个邻接表并使用 Dijkstra 算法来找到最短距离。但是，我在某些测试用例中获得正确结果时遇到问题。

以下是我的方法的简要概述：

1. 图形表示：我使用邻接列表来存储边。每条边都有正常权重和特殊权重。
2. Dijkstra 算法： 我使用最小堆优先级队列实现了 Dijkstra 算法。我维护一个距离数组来存储考虑正常权重和特殊权重的最短距离。

尽管采用了这种方法，但我还是遇到了距离计算并不总是正确的问题，并且某些测试用例失败了。具体来说，我认为问题在于我如何在边缘松弛过程中处理特殊权重。

#include <bits/stdc++.h> 
using namespace std;

typedef pair<int, int> Pair;

struct Edge {
 int v;
 int normal;
 int special;
};

int findShortestDistance(int numberOfVertices, vector<vector<int>> &adj, int src, int dst) {
 vector<vector<Edge>> adjacencyList(numberOfVertices + 1);

 // Building the adjacency list
 for (int i = 0; i < adj.size(); i++) {
     adjacencyList[adj[i][0]].push_back({adj[i][1], adj[i][2], adj[i][3]});
 }

 // Min heap priority queue
 priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
 vector<vector<int>> distanceFromSource(numberOfVertices + 1, vector<int>(2, INT_MAX));

 minHeap.push({0, src});
 distanceFromSource[src][0] = 0;

 while (!minHeap.empty()) {
     auto currentPair = minHeap.top();
     minHeap.pop();

     int currentNode = currentPair.second;
     int currentDistance = currentPair.first;

     // Exploring neighbors
     for (auto neighbor : adjacencyList[currentNode]) {
         int neighborNode = neighbor.v;
         int edgeWeight = neighbor.normal;
         int specialWeight = neighbor.special;

         // Relaxing the edge with normal weight
         if (distanceFromSource[neighborNode][0] > currentDistance + edgeWeight) {
             distanceFromSource[neighborNode][0] = currentDistance + edgeWeight;
             minHeap.push({distanceFromSource[neighborNode][0], neighborNode});
         }

         // Relaxing the edge with special weight
         if (distanceFromSource[neighborNode][1] > currentDistance + specialWeight) {
             distanceFromSource[neighborNode][1] = currentDistance + specialWeight;
             // minHeap.push({distanceFromSource[neighborNode][1], neighborNode});
         }
     }
 }

 return min(distanceFromSource[dst][0], distanceFromSource[dst][1]);
}

Answer 1

您正在使用

currentDistance

计算下一个节点的最佳路径，而不考虑该路径是否已经包含特殊边。

无需过多更改代码，您可以直接获取距

distanceFromSource

向量的距离。

只有一种方法可以在不使用特殊边的情况下创建到邻居的路径：使用迄今为止找到的到不使用特殊边的当前节点的最短路径，并通过普通边将其连接到邻居。

对于使用特殊边的路径，您可以使用到已使用特殊边的当前节点的最短路径并采用正常边到邻居，或者使用到不使用特殊边的当前节点的最短路径边，然后将特殊边带到邻居。

通过这些编辑，您的解决方案将通过：

std::vector<std::vector<int>> distanceFromSource(numberOfVertices + 1, std::vector<int>(2, 1e9));
// don't use INT_MAX as it results in overflow later

// inside the loop:
if (distanceFromSource[neighborNode][0] > distanceFromSource[currentNode][0] + edgeWeight) {
    minHeap.push({distanceFromSource[neighborNode][0] = distanceFromSource[currentNode][0] + edgeWeight, neighborNode});
}
int bestWithSpecial = std::min(distanceFromSource[currentNode][1] + edgeWeight, distanceFromSource[currentNode][0] + specialWeight);
if (distanceFromSource[neighborNode][1] > bestWithSpecial) {
    minHeap.push({
        distanceFromSource[neighborNode][1] = bestWithSpecial,
        neighborNode
    });
}

请注意，这可以进一步优化，以避免向优先级堆添加不必要的节点。