首页 > 代码库 > 单源最短路径问题
单源最短路径问题
如图,求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到本身的最短路径就是自己,且长度为0 final[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; else cout<<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语言版)》(严蔚敏、吴伟民,清华大学出版社)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。