❗ 算法描述❗：
在更新 dist 值的时候，也判断 best 的关系，并进行更新。
/* * * * * * Accordingly, for a specific starting node s, define best[u] = minimum number of edges in a shortest path from s to u. Give an efficient algorithm for the following problem. Input: Graph G = (V, E); positive edge lengths l[e]; starting node s ∈ V . Output: The values of best[u] should be set for all nodes u ∈ V . * * * * * */ #include <iostream> #include <vector> #include <stack> using namespace std; int vexnum; int edgenum; vector<vector<int>> edges; vector<int> best; vector<int> dist; int main() { cout << "请输入顶点个数、边条数:" << endl; cin >> vexnum >> edgenum; edges.resize(vexnum, vector<int>(vexnum, 0)); // edges[i][j] = 0 表示从i -> j 没有边 cout << "请输入各边的顶点序号、长度:" << endl; for (int i = 0; i < edgenum; ++i) { int tmp1, tmp2, temp; cin >> tmp1 >> tmp2 >> temp; edges[tmp1][tmp2] = temp; } //初始化 best 数组 best.resize(vexnum, INT_MAX); best[0] = 0; //初始化 dist 数组 dist.resize(vexnum, INT_MAX); dist[0] = 0; for (int i = 0; i < vexnum; ++i) { if (edges[0][i] != 0) { dist[i] = edges[0][i]; } } for (int k = 1; k < vexnum; ++k) // 更新 vexnum-1 次 { // 更新 dist[t] 和 best[t] 的值 for (int t = 1; t < vexnum; ++t) { for (int j = 0; j < vexnum; ++j) { if (edges[j][t] != 0 && dist[j] != INT_MAX) { // 找到更短的路径 if (dist[t] > dist[j] + edges[j][t]) { dist[t] = dist[j] + edges[j][t]; best[t] = best[j] + 1; } else if (dist[t] == dist[j] + edges[j][t] && best[t] > best[j] + 1) { best[t] = best[j] + 1; } } } } } for (int i = 0; i < vexnum; ++i) { cout << "best[" << i << "] = " << best[i] << endl; } return 0; }检验：
