Ⅰ 每一对顶点之间的最短路径是什么
每一对顶点之间的最短路径是指对于给定的带权有向图G=(v,E),要对G中任意一对顶点有序对(vi,vj)(vi≠vj),找出vi到vj的最短距离和vj到vi的最短距离。
解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行Dijkstra算法n次,即可求得有向图G=(v,E)中每一对顶点间的最短路径,总的时间复杂度为0(n2)。
弗洛伊德(Floyd)提出了另一个求任意两顶点之间最短路径的算法,虽然其时间复杂度也是0(n2),但算法形式更为简明,易于理解与编程。
1.弗洛伊德算法的思想弗洛伊德算法是从图的邻接矩阵开始,按照顶点v0,v1,v2,v2,…,vn的次序,分别以每个顶点vk(0≤k<n)作为新考虑的中间点,在第k-1次运算D(k-1)的基础上,求出每一对顶点之间vi到vj的最短路径长度D(k)[i][j],计算公式为:
D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}重复执行n次后,D(k)[i][j]中保留的值就是每对顶点的vi到vj的最短路径长度。
2.弗洛伊德算法的步骤(1)从图的带权邻接矩阵G.arcs[][]开始,即D(-1)=arcs[][],每次以上一次D(k-1)为基础,用公式D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}计算出D(k)[i][j]的值,即D(k-1)[i][k]+D(k-1)[k][j]<D(k-1)[i][j]才修改,若D(k)[i][j]修改过,则相应的路径P(k)[i][j]也要作相应的修改,即P(k)[i][j]=P(k-1)[i][k]+P(k-1)[k][j]。
(2)重复上述过程n次后,D(k)[i][j]中保存的就是每一对顶点的最短路径长度,P(k)[i][j]中保存的就是每一对顶点的最短路径。
说明:从计算公式可以看出,i=j是对角线上的元素;i=k是i行上的元素;j=k是j列上的元素,这些特殊的顶点不用计算,保留原来的数据值。因此,计算的数据元素减少了很多。
Ⅱ 以邻接表作存储结构实现求源点到其余各顶点的最短路径的Dijkstra算法
具体算法为:
//Dijkstra求单源最短路径
#include<stdio.h>
#define N 20 //图的顶点最多数
#define MAX 1000
#define MIN -1
typedef int ElemType;//图的顶点标识,这里为自然数
//图的结点结构
typedef struct ArcNode{
ElemType adjvex;//图的顶点 (该弧指向顶点的位置)
struct ArcNode *nextarc;//指向下一条弧的指针
int info//该弧权值
}ArcNode;
//表头结点表
typedef struct VertexNode{
ElemType data;
ArcNode *firstarc;
}VertexNode;
//图
typedef struct AdjList{
VertexNode vertex[N];
int vexnum;//图的顶点数
int arcnum;//弧数;
int kind;//图的种类(kind=1为有向图)
int dist[N];//图的路径长度
int path[N];//辅助数组
}AdjList;
//边
typedef struct{
int i;
int j;
int f;
}Side;
//邻接表法创建图
int CreateDAG(AdjList *L){
int i,j;
ArcNode *p=NULL;
//测试用例
Side S[N];
S[0].i=1;S[0].j=3;S[0].f=10;
S[1].i=1;S[1].j=5;S[1].f=30;
S[2].i=1;S[2].j=6;S[2].f=100;
S[3].i=2;S[3].j=3;S[3].f=5;
S[4].i=3;S[4].j=4;S[4].f=50;
S[5].i=4;S[5].j=6;S[5].f=10;
S[6].i=5;S[6].j=6;S[6].f=60;
S[7].i=5;S[7].j=4;S[7].f=20;
for(i=1;i<7;i++){
L->vertex[i].data=i;
L->dist[i]=MAX;//设为最大值,表示不可达
L->path[i]=MIN;//设为最小值,表示尚未初始化
//L->vertex[i].indegree=0;
L->vertex[i].firstarc=NULL;
}
L->kind=1;
L->vexnum=6;
L->arcnum=8;
for(i=0;i<8;i++){
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=S[i].j;
p->info=S[i].f;
p->nextarc=L->vertex[(S[i].i)].firstarc;
L->vertex[(S[i].i)].firstarc=p;
if(S[i].i==1){//初始顶点为1
L->dist[(S[i].j)]=S[i].f;
//L->path[(S[i].j)]=S[i].f;
}
// L->vertex[(S[i].j)].indegree++;
}
return 1;
}
//输出邻接表存储
void PrintALGraph(AdjList *L){
ArcNode *p=NULL;
int i,k=0;
for(i=1;i<=L->vexnum;i++){
k=L->vertex[i].data;
printf("V%d",k);
// printf(" 入度为%d 邻接点有 ",(L->vertex[i].indegree));
p=L->vertex[k].firstarc;
while(p!=NULL){
printf(" ->%d",p->adjvex);
p=p->nextarc;
}
printf("
");
}
}
//Dijkstra求单源最短路径
void Dijkstra(AdjList *L){
int i=1,j,k=0;
Side s;
L->path[1]=0;
ArcNode *p=NULL;
while(k<10){
s.f=MAX;
for(i=1;i<=L->vexnum;i++){
if(L->path[i]!=MIN){
p=L->vertex[i].firstarc;
if(p!=NULL){
while(p!=NULL){
if(s.f>p->info&&L->path[(p->adjvex)]==MIN){
s.f=p->info;
s.i=i;
s.j=p->adjvex;
}
p=p->nextarc;
}
}
}
}
if(s.f==MAX){
}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){
L->dist[(s.j)]=L->dist[(s.i)]+s.f;
L->path[(s.j)]=L->dist[(s.j)];
}else{
L->path[(s.j)]=L->dist[(s.j)];
}
k++;
}
//输出
printf("输出最短路径:
");
for(i=1;i<=L->vexnum;i++){
if(L->dist[i]==1000||i==1){
printf("v1到v%d不存在最短路径
",i);
}else{
printf("v1到v%d的最短路径是%d
",i,L->dist[i]);
}
printf("path is %d
",L->path[i]);
}
}
int main(){
AdjList *L=(AdjList *)malloc(sizeof(AdjList));
if(CreateDAG(L)==1){
PrintALGraph(L);
Dijkstra(L);
}else{
printf("创建失败
");
}
}
(2)有向图最短路径java扩展阅读:
要求带权有向图中某一顶点到其他各顶点的最短路径,常用Dijkstra算法,该算法基本思想是,先将图的顶点分为两个集合,一个为已求出最短路径的终点集合(开始为原点v1),另一个为还未求出最短路径的顶点集合(开始为除v1外的全部结点),然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。
算法中使用dist数组,dist[i]表示目前已经找到、v1到vi的当前最短路径,否则为MAX;path数组,作为是否找到该点最短路径的标志,path[i]==MIN表示为未找到,否则为最短路径值。