代码如下
#include<iostream>using namespace std;#define maxint 32767int secl(int* s, int* dist, int n) {int v = maxint;for (int i = 1; i <= n; i++) {if (s[i] == 0) {if (dist[i] < v) {v = dist[i];}}}for (int i = 1; i <= n; i++) {if (dist[i] == v) {return i;}}}void Dijkstra(int n, int v, int dist[], int prev[], int** c) {int* s = new int[n + 1];memset(s, 0, sizeof(s) * (n + 1));for (int i = 1; i <= n; i++) {dist[i] = c[v][i];if (dist[i] == maxint) {prev[i] = 0;}else {prev[i] = v;}}dist[v] = 0;for (int i = 1; i <= n; i++) {cout << dist[i] << ' ';}cout << endl;s[v] = 1;for (int i = 2; i <= n; i++) {int flag = secl(s, dist, n);s[flag] = i;for (int j = 1; j <= n; j++) {if (c[flag][j] < maxint) {int newdist = dist[flag] + c[flag][j];if (newdist < dist[j]) {dist[j] = newdist;prev[j] = flag;}}}for (int i = 1; i <= n; i++) {cout << dist[i] << ' ';}cout << endl;}for (int i = 1; i <= n; i++) {cout << s[i] << ' ';}cout << endl;}/*for (int i = 1; i<n; i++) {int temp = maxint;int u = v;for (int j = 1; j <= n; j++) {int road=0;if ((!s[j]) && (dist[j]<temp)) {u=j;cout << u << endl;temp=dist[j];}s[u] = true;for (int j = 1; j <= n; j++) {if ((!s[j]) && (c[u][j] < maxint)) {Type newdist = dist[u] + c[u][j];if (newdist < dist[j]) {dist[j] = newdist;prev[j] = u;}}}for (int ii = 1; ii <= n; ii++) {cout << dist[ii] << ' ';}cout << endl;}}*/int main() {int n;cin >> n;int v;cin >> v;int** c = new int* [n + 1];for (int i = 0; i <= n; i++) {c[i] = new int[n + 1];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> c[i][j];}}int* dist = new int[n + 1];int* prev = new int[n + 1];Dijkstra(n, v, dist, prev, c);for (int i = 1; i <= n; i++) {cout<<dist[i]<<' ';}cout << endl;for (int i = 1; i <= n; i++) {cout << prev[i] << ' ';}return 0;}/*测试数据5 10 10 32767 30 100 32767 0 50 32767 3276732767 32767 0 32767 1032767 32767 20 0 6032767 32767 32767 32767 0*//*7 10 20 50 30 32767 32767 3276732767 0 25 32767 32767 70 3276732767 32767 0 40 25 50 3276732767 32767 32767 0 55 32767 3276732767 32767 32767 32767 0 10 7032767 32767 32767 32767 32767 0 5032767 32767 32767 32767 32767 32767 0 */
注释掉的代码为《算法设计与分析》第五版的源代码，个人感觉有点问题，不知道是不是我敲错了，欢迎各位大牛评论探讨。
运行截图：
参考资料：《算法设计与分析》第五版
