导航:首页 > 编程语言 > 有向图最短路径java

有向图最短路径java

发布时间:2023-09-07 10:02:50

Ⅰ 每一对顶点之间的最短路径是什么

每一对顶点之间的最短路径是指对于给定的带权有向图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表示为未找到,否则为最短路径值。

阅读全文

与有向图最短路径java相关的资料

热点内容
小米桌面文件夹乱码怎么回事 浏览:858
点歌台app怎么连接 浏览:318
大学电脑编程学什么好 浏览:348
上哪里取消应用加密 浏览:172
电气控制与可编程控制器pdf 浏览:87
cad图纸不能跨文件夹粘贴 浏览:256
学生云服务器主机 浏览:889
单片机状态周期 浏览:622
lua中的android 浏览:443
加密贵还是植发贵 浏览:664
阳光压缩机继电器 浏览:971
修改阿里云服务器密码 浏览:817
lk4102加密芯片 浏览:588
怎么更改app店面 浏览:489
设备部门如何做好服务器 浏览:849
androido下载 浏览:478
神奇高量战法副图源码 浏览:830
汇编语言设计凯撒密码加密器 浏览:392
主次梁加密是加在哪里 浏览:664
模板匹配算法matlab 浏览:825