-
最短路径:指两顶点之间经过的边上的权值之和最小的路径,并称路径的第一个顶点为源点,最后一个顶点为终点 - 求最短路径的算法通常都依赖一种性质:两点之间的最短路径也包含了路径上 其他顶点之间的最短路径
- 带权有向图G的最短问题分两类:
-
单源最短路径:即某一顶点到其他各顶点的最短路径,可用Dijkstra算法求 -
任意一对顶点最短路径:可通过Floyd-Warshall算法求解
-
Dijkstra算法(迪杰斯特拉算法)代码实现
#include <iostream>
#include<stdlib.h>
#define maxSize 100
#define infinity 65535
using namespace std;
typedef struct{//邻接矩阵构造的图结点
char vnode[maxSize];
int edge[maxSize][maxSize];
int n,e;
}MGraph;
void createMGraph(MGraph &G){//创建图
int i,j,n,e,k,w;
cout<< "请输入图的顶点数和边数"<<endl;
cin>> G.n >> G.e;
n=G.n;
e=G.e;
cout<< "请输入顶点"<<endl;
for(i=0;i<n;i++){
cin>> G.vnode[i];
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
G.edge[i][j]=infinity;
}
}
cout<< "请输入边的下标和权值:i j w"<<endl;
for(k=0;k<e;k++){
scanf("%d %d %d",&i,&j,&w);
G.edge[i][j]=w;
G.edge[j][i]=G.edge[i][j];
}
}
void shortPath_Dijkstra(MGraph G,int v,int path[],int distance[]){//最短路径(顶点v到各顶点的最小距离)
int i,j,k,t,min;
int final[maxSize];
for(i=0;i<G.n;i++){
final[i]=0;//初始化,刚开始生成树里没顶点
distance[i]=G.edge[v][i];//开始顶点v与其他顶点的距离(若v与其他顶点没有交集,则距离为infinity)
path[i]=0;//能构成最小路径的顶点的下标
}
distance[v]=0;//自己与自己的距离为0
final[v]=1; //把起始顶点v加入到生成树中
for(t=1;t<G.n;t++){
min=infinity;
for(j=0;j<G.n;j++){
if(final[j]==0&&distance[j]<min){
min=distance[j];//找出distance中的最小值(剔除已加入生成树的顶点,不然min就为0了)
k=j;//distance的下标都是以final[v]为起点构成边的终止顶点,distance值为边的权值
}
}
final[k]=1;//把终止顶点k放入生成树
for(i=0;i<G.n;i++){//min就代表了final[i]=1的那部分顶点到k顶点构成的最小路径的值
if(final[i]==0&&(min+G.edge[k][i]<distance[i])){//若有多条分支到某个顶点的距离比直接去更短则更新
distance[i]=min+G.edge[k][i];//若开始顶点v与i顶点没交集,而k与i相邻接,则v与i的距离就记作min+k与i的距离
//若v与i有交集,且k与i也有交集,若min+k与i的距离比v与i的距离短则更新
path[i]=k;//顶点i的前驱顶点为k (与终止顶点i配套的起始顶点为k)
//若找到了v与i更近的路径,则更新与i相邻的顶点即为k
//接下来的循环就是找与k顶点相邻接的终止顶点中构成路径最小的那个,然后放入生成树
}
}
}
}
int main(int argc, char** argv) {
MGraph G;
int path[maxSize];
int distance[maxSize];
createMGraph(G);
shortPath_Dijkstra(G,0,path,distance);//迪杰斯特拉算法
for(int i=0;i<G.n;i++){
printf("path[%d]=%d,distance[%d]=%d\n",i,path[i],i,distance[i]);
}
return 0;
}
/* 示例输入: 顶点数和边数: 9 15 输入顶点: 0 1 2 3 4 5 6 7 8 输入顶点下标和权值: 4 7 7 2 8 8 0 1 10 0 5 11 1 8 12 3 7 16 1 6 16 5 6 17 1 2 18 6 7 19 3 4 20 3 8 21 2 3 22 3 6 24 4 5 26 */