dijkstra算法-最短路径（包含路径记录）
2019-11-06 07:08:35
供稿：网友
#include <iostream>#include <stack>using namespace std;#define MAX 999#define BIG 101int a[BIG][BIG];int dist[BIG]; //储存起点到其他点的最短路径int book[BIG]; //标记数组int path[BIG];stack<int> pathout;void output_path(int end){int i = end;int flag = 1;int sum = 0;while (flag == 1){sum++;pathout.push(i); //压栈if (path[i] == 0) flag = 2;else i = path[i]; //指向该点的上一个点}cout << "前进路径为：";while (!pathout.empty()){cout << pathout.top() << " "; //栈顶出栈if (sum > 1){sum--;cout << "-> ";}pathout.pop(); // 移除栈顶}cout << endl;}void dijkstra(int sta, int end, int m,int n) //dijkstra 核心代码{while (book[end] != 1){int min_i;int min = MAX;//////////////for (int i = 1; i <= m; i++) //找出未标记的点中 里起点最近的{if (book[i] == 0 && dist[i] < min){min = dist[i];min_i = i;}}/////////////////book[min_i] = 1;for (int i = 1; i <=m; i++) //松弛 {//cout <<"i="<< i << endl;if (a[min_i][i] < MAX){if (dist[i] > dist[min_i] + a[min_i][i]){dist[i] = dist[min_i] + a[min_i][i];path[i] = min_i;}}}}}int main(){int m, n;cout << " 欢迎使用路径规划系统" << endl << endl;;while (cout << "输入地点和街道的数目：", cin >> m >> n){if(m<2||n<(m-1||n>(m*(m-1)/2))){cout << "输入有误" << endl << endl;}else{//以下是初始化memset(dist, MAX, sizeof(dist));memset(book, 0, sizeof(book));memset(path, 0, sizeof(path));for (int i = 0; i < BIG; i++){for (int j = 0; j < BIG; j++){if (i == j) a[i][j] = 0;else a[i][j] = MAX;}}//////////////////////////////////int x, y, z;cout << "输入街道的信息：" << endl;for (int i = 1; i <= n; i++){cin >> x >> y >> z;a[x][y] = z;}int sta;int end;cout << "输入出发地点与目的地：" << endl;cin >> sta >> end;///////////////////////int min_i = MAX;for (int i = 1; i <= m; i++){dist[i] = a[sta][i]; //起点与其余点的距离if (dist[i]<MAX&&dist[i] > 0 && dist[i] < min_i) min_i = i;}path[min_i] = sta;book[sta] = 1;//////////////////////dijkstra(sta, end,m,n);//////////////////////cout << "出发地点到目的地的最短距离为：" << dist[end] << endl;output_path(end);}cout << "是否继续查询？ Y or N : ";char c;cin >> c;if (c == 'N' || c == 'n'){cout << " 感谢使用！再见" << endl << endl;getchar();getchar();return 0;}}}
