代码如下:
#include <iostream>using namespace std;const int N = 30;typedef char ElemType;const double noEdge = 99999;class Graph{private:double G[N][N];int vertexN, edgeN;double dist[N];bool vis[N];int path[N];int sv;ElemType data[N];int findMinDist(){double minDist = noEdge;int v = -1;for (int i = 0; i < vertexN; i++){if (!vis[i] && dist[i] < minDist){minDist = dist[i];v = i;}}return v;}public :Graph(){for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){G[i][j] = noEdge;}}cout << "vertexN = ? and edgeN = ?" << endl;cin >> vertexN >> edgeN;for (int i = 0; i < vertexN; i++){cin >> data[i];}cout << "Please input information of edge(including weight)" << endl;for (int i = 0; i < edgeN; i++){int v1, v2;double w;cin >> v1 >> v2 >> w;G[v1][v2] = w;}}bool dijkstra(int s){sv = s;for (int i = 0; i < vertexN; i++){dist[i] = G[s][i];if (dist[i] < noEdge){path[i] = s;}else{path[i] = -1;}vis[i] = false;}dist[s] = 0;vis[s] = true;while (true){int v = findMinDist();if (v == -1) break;vis[v] = true;for (int w = 0; w < vertexN; w++){if (!vis[w] && G[v][w] < noEdge)if (G[v][w] < 0) return false;if (dist[w] > dist[v] + G[v][w]){dist[w] = dist[v] + G[v][w];path[w] = v;}}}return true;}void printPath(int o){cout << "value = " << dist[o] << endl;if (dist[o] < noEdge){while (path[o] != sv){cout << data[o] << " <- " << data[path[o]] << endl;o = path[o];}cout << data[o] << " <- " << data[path[o]] << endl;}else{cout << "The road is death" << endl;}}};int main(){Graph g;int s;cin >> s;g.dijkstra(s);int o;cin >> o;g.printPath(o);return 0;}
测试如下:
