要检查图表的两个中心之间的给定路径是否符合最短路径，可以通过使用可靠的最短路径将沿给定路径的整个边缘权重与相同中心组合之间的最短距离进行比较方式计算，例如 Dijkstra 计算或 Floyd−Warshall 计算。如果给定路径上的所有边权重与最有限的删除相匹配，那么它就代表最简单的路径。另外：如果整个边权重比最短距离更突出，则表明图表中两个中心之间存在较短的距离。
使用的方法
-
Dijkstra 算法
-
具有边缘反转成本的 Floyd−Warshall 算法
贪心算法
Dijkstra 的计算可能是一种流行的图表遍历计算，用于发现图表中源中心与所有其他中心之间最有限的路径。在检查两个中心之间的给定路径是否与最有限路径相关的情况下，Dijkstra 的计算可用于计算这些中心之间的最有限间隔。通过从起始枢纽运行 Dijkstra 的计算，我们得到所有其他枢纽的最有限的间隔。如果给定的路线与两个枢纽之间的最有限距离相匹配，那么它就表示一条实质性且最短的路线。其他：如果给定的路线比计算的最短距离长，则表明图表中存在更短的路线。
算法
-
创建最短路径（图形、源、目的地）：
-
初始化一组“过去”来存储去往中心的距离，并初始化一个单词参考间隔来存储最有限的距离。
-
在分隔字典中将源集线器的间隔设置为无限，并将所有其他中心的间隔设置为无限。
-
虽然存在未访问的节点，
-
a。选择与分隔词参考距离最小的中心并将其标记为已访问。
-
b。对于当前节点的每个邻居集线器：
-
通过将边权重添加到当前节点的距离来计算临时间隔。
-
如果条件间距小于存放间距，则检修距离。
-
如果在分离中从源到目标的最短距离与给定路径长度收支平衡，则返回 true（给定路径表示最短路径）。其他情况，返回 false。
-
此计算利用 Dijkstra 方法来计算最短间隔，然后将从源到目标的最短距离与给定的路径长度进行比较，以确定是否是最短的路径.
示例
#include
#include
#include
#include
using namespace std;
const int INF = numeric_limits::max();
bool shortestPath(vector& graph, int source, int destination, int pathLength) {
int numNodes = graph.size();
vector distances(numNodes, INF);
distances[source] = 0;
priority_queue pq;
pq.emplace(0, source);
while (!pq.empty()) {
int u = pq.top().second;
int dist = pq.top().first;
pq.pop();
if (dist > distances[u])
continue;
for (auto& neighbor : graph[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (dist + weight < distances[v]) {
distances[v] = dist + weight;
pq.emplace(distances[v], v);
}
}
}
return (distances[destination] == pathLength);
}
int main() {
int numNodes = 6;
vector graph(numNodes);
// Build the graph
graph[0].emplace_back(1, 2);
graph[0].emplace_back(2, 5);
graph[1].emplace_back(3, 4);
graph[1].emplace_back(4, 1);
graph[2].emplace_back(3, 2);
graph[3].emplace_back(4, 3);
graph[3].emplace_back(5, 6);
graph[4].emplace_back(5, 2);
int source = 0;
int destination = 5;
int pathLength = 8;
bool isShortestPath = shortestPath(graph, source, destination, pathLength);
if (isShortestPath)
cout
