今天看算法导论上的Dijkstra算法,其本质思想就是一个贪心策略。我使用节点的编号来维持最小优先队列,每次取集合V-S中节点值最小的点加入S。时间复杂度为n的平方(n为图的节点数)。书上说如果是稀疏图,用二叉堆或者斐波那契堆实现可以降低时间复杂度,这个我没有验证。
直接上代码:
#include <iostream> #include <stdlib.h> #include <cstdlib> using namespace std; const int VertexNum = 5;//节点个数 const int MAX = 100000;//节点值和路径权重的上限 int main() { int GraphMatrix[VertexNum][VertexNum];//存储图的矩阵 int used[VertexNum];//标记节点是否已经加入当前的最短路径集合 int predecessor[VertexNum];//节点的前驱 int VertexValue[VertexNum];//保存当前从源节点到该节点的最短路径值 FILE *fp;//文件指针,用于打开txt文件读取图的邻接矩阵 int i,j,k; int weight;//路径的权重 //初始化邻接矩阵 for(i = 0;i < VertexNum;i++) for(j = 0;j < VertexNum;j++) GraphMatrix[i][j] = MAX; //初始化节点的值、标记和前驱 for(i = 0;i < VertexNum;i++) { VertexValue[i] = MAX; used[i] = 0; predecessor[i] = 0; } //打开文件 fp = fopen("F:\\Dijkstra.txt","r");//F:\\Dijkstra.txt是文件路径 if(!fp) { cout<<"打开文件失败"<<endl; return -1; } //读取文件中的值,保存在图的邻接矩阵中 while(fscanf(fp,"%d%d%d",&i,&j,&weight) != EOF) { GraphMatrix[i][j] = weight; } VertexValue[0] = 0; k = 0; //遍历所有节点,将它加入到最短路径节点集合 for(i = 1;i < VertexNum;i++) { //对每条边做松弛操作 for(j = 1;j < VertexNum;j++) { if( (!used[j]) && (GraphMatrix[k][j]+VertexValue[k] < VertexValue[j])) { VertexValue[j] = GraphMatrix[k][j]+VertexValue[k]; predecessor[j] = k; } } used[k] = 1; int t = k; int temp = MAX; //找出V-S集合中值最小的节点 for(int m = 0;m < VertexNum;m++) { if(!used[m] && temp > VertexValue[m]) { temp = VertexValue[m]; k = m; } } //输出最短路径,格式为“前驱节点 节点 最短路径值” cout<<predecessor[k]<<" "<<k<<" "<<VertexValue[k]<<endl; } cin>>i;//为了不让输出结果的控制台一闪而过 return 0; }
输入:
txt文件内容:
0 1 10
0 2 5
1 2 2
1 3 1
2 1 3
2 3 9
2 4 2
3 4 4
4 0 7
4 3 6
输出结果: