如图，求V0到其他顶点的最短路径及其长度，
废话少说，用Dijkstra算法。我在《数据结构（C语言版）》里面的代码的基础上写了一个直接保存路径的版本。看代码，
#include<iostream>#include<vector>using namespace std;#define MAXINT 1000000// src -- 为源节点// g[][] -- 有向图的邻接矩阵// v[] -- v[j]是从src到j的最短路径// dist[] -- dist[k]为从src到k的最短路径的长度template<int m>vector<int>* djst(const int (&g)[m][m], int* dist, int src){//final[] -- final[i]为true，则已求得从src到i的最短路径bool *final = new bool[m];vector<int> *v = new vector<int>[m];for(int i = 0; i < m; ++i){final[i] = false;dist[i] = g[src][i];// 从src到i的最短路径初始化为当前从src到i的边的长度if(dist[i] < MAXINT){// 若src能直接到达i，则目前，存在从src到i的最短路径，v[i].push_back(src);// 于是，把src和i都存入作为路径v[i].push_back(i);}}dist[src] = 0; // src到本身的最短路径就是自己，且长度为0final[src] = true;v[0].push_back(0);for(int i = 1; i < m; ++i){ // 还有num-1个节点没有求出最短路径int min = MAXINT;int nearest = 0;for(int j = 0; j < m; ++j){if(!final[j])// 找出与src最近的一个节点j，并且，目前从src到j的最短路径还没求出来if(dist[j] < min){nearest = j;min = dist[j];}}final[nearest] = true;// 则从src到nearest的最短路径已经找到for(int k = 0; k < m; ++k){ // 更新当前最短路径和距离if(!final[k] && (min + g[nearest][k] < dist[k]) ){ // 若经过nearest到达k的路径比原来的路径还短，dist[k] = min + g[nearest][k]; // 则把进过nearest到达k的路径设为最短路径v[k] = v[nearest]; // 把src->nearest->k 作为src到k的最短路径v[k].push_back(k);}}}return v;}//打印出最短路径void printPath(vector<int> * v, int len){for(int i = 0; i < len; ++i){cout<<"from 0 to "<<i<<": ";if(v[i].size() == 0){cout<<"None"<<endl;continue;}for(int j = 0; j < v[i].size(); ++j){if(j != 0)cout<<"->";cout<<v[i][j];}cout<<endl;}}void printArray(int *a, int len){for(int i = 0; i < len; ++i){cout<<"length from 0 to "<<i<<": ";if(a[i] == MAXINT)cout<<"MAXINT"<<endl;elsecout<<a[i]<<endl;} cout<<endl;}int main(){int dist[6];int g[6][6] = { //定义图的邻接矩阵MAXINT, MAXINT, 10, MAXINT, 30, 100,MAXINT, MAXINT, 5, MAXINT, MAXINT, MAXINT,MAXINT, MAXINT, MAXINT, 50, MAXINT, MAXINT,MAXINT, MAXINT, MAXINT, MAXINT, MAXINT, 10,MAXINT, MAXINT, MAXINT, 20, MAXINT, 60,MAXINT, MAXINT, MAXINT, MAXINT, MAXINT};vector<int> *v;v = djst(g, dist, 0);cout<<endl<<"-----------------------------Dijkstra------------------------------"<<endl;printArray(dist, 6);printPath(v, 6);cout<<"-------------------------------------------------------------------"<<endl;return 0;}
运行结果如图，
搞定。
参考：
《数据结构（C语言版）》（严蔚敏、吴伟民，清华大学出版社）版权声明：本文为博主原创文章，未经博主允许。
