首页 > 代码库 > 最短路径:Dijkstra算法的实现(邻接矩阵)
最短路径:Dijkstra算法的实现(邻接矩阵)
</pre><pre name="code" class="cpp"> #include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<vector> using namespace std; const int INF = 0x3f3f3f3f;//无穷大 const int maxn = 20;//顶点个数的最大值 int n;//顶点个数 int edge[maxn][maxn];//邻接矩阵 //Dijkstra算法用到的3个数组 int s[maxn];//记录顶点是否在集合中 int dist[maxn];//记录路径的权值 int path[maxn];//记录路径 void Dijkstra( int v0 )//求v0到其他点的最短路径 { int i, j, k;//循环变量 for(i=0; i<n; i++) { dist[i] = edge[v0][i]; s[i] = 0; if( i!=v0 && dist[i]<INF ) path[i] = v0; else path[i] = -1; } s[v0] = 1; dist[v0] = 0;//顶点v0加入顶点集合s for(i=0; i<n-1; i++)//从顶点v0确定n-1条最短路径 { int min = INF, u = v0; //选择当前集合T中具有最短路径的顶点u for(j=0; j<n; j++) { if( !s[j] && dist[j]<min ) { u = j; min = dist[j]; } } s[u] = 1;//将顶点u加入集合s,表示它的最短路径已求得 //修改T集合中顶点的dist和path数组元素 for(k=0; k<n; k++) { if( !s[k] && edge[u][k]<INF && dist[u]+edge[u][k]<dist[k] ) { dist[k] = dist[u] + edge[u][k]; path[k] = u; } } } } int main() { int i, j;//循环变量 int u, v, w;//边的起点和终点以及权值 scanf("%d", &n);//读入顶点个数n while(1) { scanf("%d%d%d", &u, &v, &w); if( u==-1 && v==-1 && w==-1 ) break; edge[u][v] = w;//构建邻接矩阵 } for(i=0; i<n; i++) { for(j=0; j<n; j++) { if( i==j ) edge[i][j] = 0; else if( edge[i][j] == 0 ) edge[i][j] = INF; } } Dijkstra(0);//求顶点0到其他顶点的最短路径 int shortest[maxn];//输出最短路径上的各个顶点时存放各个顶点的序号 for(i=1; i<n; i++) { printf("%d\t", dist[i]);//输出顶点0到顶点i的最短路径长度 //以下代码用于输出顶点0带顶点i的最短路径 memset( shortest, 0, sizeof(shortest) ); int k = 0;//k表示shorttest数组中最后一个元素的下标 shortest[k] = i; while( path[ shortest[k] ]!=0 ) { k++; shortest[k] = path[shortest[k-1]]; //printf("%d ", k); } k++; shortest[k] = 0; //printf("%d", k); for(j=k; j>0; j--) printf("%d--", shortest[j]); printf("%d\n", shortest[0]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。