编程实现动态规划求解每对结点之间的最短路径问题算法代码.zip

#include <iostream> using namespace std; const int INF = 99999999; int main() { int e[10][10], n, m, t1, t2, t3; cin >> n >> m; //n表示顶点个数，m表示边的条数 for (int i = 1; i <= n; i++)//初始化邻接表 { for (int j = 1; j <= n; j++) { if (i == j) e[i][j] = 0; else e[i][j] = INF; } } for (int i = 1; i <= m; i++)//定义邻接表 { cin >> t1 >> t2 >> t3; e[t1][t2] = t3; } //核心代码 for (int k = 1; k <= n; k++)//每个顶点都作为一次中转点 { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j]; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout<< i <<"到"<<j<<"距离为"<< e[i][j]; cout << endl; } } return 0; } /* 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 */ // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单 // 调试程序: F5 或调试 >“开始调试”菜单 // 入门使用技巧: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件