数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++ Dijkstra 最短路径算法程序？
Dijkstra算法（或Dijkstra最短路径优先算法，SPF算法）是一种用于查找图中节点之间最短路径的算法，例如，它可以表示道路网络。该算法从起始顶点（源点）创建一个到图中所有其他点的最短路径树。
Dijkstra算法通过构建一个集合，其中包含与源点距离最小的节点，来查找从单个源节点到所有其他节点的最短路径树。
图包含以下内容：
顶点或节点，在算法中用v或u表示。
连接两个节点的加权边：(u,v)表示一条边，w(u,v)表示其权重。在右图中，每条边的权重都以灰色显示。
算法步骤
- 将所有顶点的距离设置为无穷大，除了源顶点，将源顶点的距离设置为0。
- 以(距离，顶点)的形式将源顶点压入最小优先级队列，因为最小优先级队列中的比较将根据顶点的距离进行。
- 从优先级队列中弹出距离最小的顶点（首先弹出的顶点=源点）。
- 如果“当前顶点距离 + 边权重 < 下一个顶点距离”，则更新与弹出顶点相连的顶点的距离，然后将具有新距离的顶点压入优先级队列。
- 如果之前已访问过弹出顶点，则只需继续，无需使用它。
- 重复执行相同的算法，直到优先级队列为空。
给定一个图和图中的源顶点，查找从源点到给定图中所有顶点的最短路径。给定图的权重矩阵G[][]，图中顶点的数量n，起始节点u。
输入
G[max][max]={{0,1,0,3,10},
{1,0,5,0,0},
{0,5,0,2,1},
{3,0,2,0,6},
{10,0,1,6,0}}
n=5
u=0输出
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
解释
从邻接矩阵adj[ ][ ]创建代价矩阵C[ ][ ]。C[i][j]是从顶点i到顶点j的代价。如果顶点i和j之间没有边，则C[i][j]为无穷大。
数组visited[ ]初始化为零。
for(i=0;i<n;i++) visited[i]=0;
如果顶点0是源顶点，则将visited[0]标记为1。
创建距离矩阵，存储从源顶点0到顶点0到n-1的代价。
for(i=1;i<n;i++) distance[i]=cost[0][i];
最初，源顶点的距离取为0，即distance[0]=0;
for(i=1;i<n;i++) visited[i]=0;
选择一个顶点w，使得distance[w]最小且visited[w]为0。将visited[w]标记为1。
重新计算从源点到剩余顶点的最短距离。
只有数组visited[ ]中未标记为1的顶点才应考虑重新计算距离。即对于每个顶点v
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
示例
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}
更新于：2019年8月9日
15K+ 次浏览
广告