迪杰斯特拉算法求最短距离

首页 > 代码库 > 迪杰斯特拉算法求最短距离

迪杰斯特拉算法求最短距离

2024-07-14 10:37:24 225人阅读

头文件：

#include <memory.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#include ".\source\common.h"
#include "lxbasic.h"

#define MAX_VEX_NUM 20
#define MAX_STR_LEN 20

#define INFINITY 999 //无穷大

//顶点结构
typedef struct tagVexType
{
int index;
char name[MAX_STR_LEN];
}VexType;

//弧结构
typedef struct tagArcType
{
int adj;//权值
}ArcType;

//图结构
typedef struct tagGraphic
{
VexType vexs[MAX_VEX_NUM];
ArcType arcs[MAX_VEX_NUM][MAX_VEX_NUM];
int vexnum;
int arcnum;//暂时无用
}Graphic;

//保存顶点V0到其余各顶点的最短路径权值和经过的节点路径
typedef struct tagPathFinal
{
int v0;//起始顶点编号
int D[MAX_VEX_NUM]; //最短路径的值(D[V])
int P[MAX_VEX_NUM][MAX_VEX_NUM]; //最短路径的路径(P[v])
}PathFinal;

//函数申明
//创建并初始化图
Graphic *CreateGraphic();

//画图打印
void PrintGraphic(Graphic *pGraphic);

//画图设置值
void SetGraphic(Graphic *pGraphic);

//销毁图
void DestroyGraphic(Graphic **ppGraphic);

//打印最短路径
void PrintShortestPath(Graphic *pGraphic,PathFinal *path);

//迪杰斯特拉求最短路径
void ShortestPath_DIJ(Graphic *pGraphic, PathFinal *path);

//测试程序
void TestCaseForGraphic();

源文件：////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "dc_graph.h"

/*
关于返回局部指针变量的总结：
局部变量的指针是不能返回的，而局部指针变量是可以返回的。
1.局部变量的指针和局部指针变量是两个不同概念
2.局部变量在函数体结束后生命期也结束，它的指针（即它的地址）是无效变量的地址，所以函数不能返回这种地址值
3，局部指针变量在函数结束后生命期也结束，但它指向的变量或函数或任何存储实体的生命期没有结束，函数返回的指针（地址）就是有效的
*/

//创建并初始化图
Graphic *CreateGraphic()
{
Graphic *pGraphic = (Graphic *)malloc(sizeof(Graphic));

NULL_PTR_RET_NULL(pGraphic)

pGraphic->vexnum = 0;
pGraphic->arcnum = 0;
memset(pGraphic->vexs,0,sizeof(VexType)*MAX_VEX_NUM);
memset(pGraphic->arcs,0,sizeof(ArcType)*MAX_VEX_NUM*MAX_VEX_NUM);

return pGraphic;
}

//画图
void PrintGraphic(Graphic *pGraphic)
{
int i,j;

for(i=0;i<pGraphic->vexnum;i++)
{
printf(" %s[%d] ",pGraphic->vexs[i].name,pGraphic->vexs[i].index);
}
printf("\n");

for(i=0;i<pGraphic->vexnum;i++)
{
printf("%s[%d]:",pGraphic->vexs[i].name,pGraphic->vexs[i].index);
for(j=0;j<pGraphic->vexnum;j++)
{
printf("%d ",pGraphic->arcs[i][j]);
}
printf("\n");
}
}

//设置图的顶点和邻接矩阵信息(数据结构严蔚敏版187页图7.34)
/*
vex0[0] vex1[1] vex2[0] vex3[0] vex4[0] vex5[0]
vex0[0]: 0 * 10 * 30 100
vex1[1]: * 0 5 * * *
vex2[0]: 10 5 0 50 * *
vex3[0]: * * 50 0 20 10
vex4[0]: 30 * * 20 0 60
vex5[0]: 100 * * 10 60 0
*/
void SetGraphic(Graphic *pGraphic)
{
int i,j;
NULL_PTR_RET(pGraphic)

pGraphic->vexnum = 6;
pGraphic->arcnum = 8;

pGraphic->vexs[0].index = 0;
strncpy(pGraphic->vexs[0].name,"vex0",MAX_STR_LEN);

pGraphic->vexs[1].index = 1;
strncpy(pGraphic->vexs[1].name,"vex1",MAX_STR_LEN);

pGraphic->vexs[2].index = 0;
strncpy(pGraphic->vexs[2].name,"vex2",MAX_STR_LEN);

pGraphic->vexs[3].index = 0;
strncpy(pGraphic->vexs[3].name,"vex3",MAX_STR_LEN);

pGraphic->vexs[4].index = 0;
strncpy(pGraphic->vexs[4].name,"vex4",MAX_STR_LEN);

pGraphic->vexs[5].index = 0;
strncpy(pGraphic->vexs[5].name,"vex5",MAX_STR_LEN);

pGraphic->arcs[0][0].adj = 0;
pGraphic->arcs[0][1].adj = INFINITY;
pGraphic->arcs[0][2].adj = 10;
pGraphic->arcs[0][3].adj = INFINITY;
pGraphic->arcs[0][4].adj = 30;
pGraphic->arcs[0][5].adj = 100;

pGraphic->arcs[1][1].adj = 0;
pGraphic->arcs[1][2].adj = 5;
pGraphic->arcs[1][3].adj = INFINITY;
pGraphic->arcs[1][4].adj = INFINITY;
pGraphic->arcs[1][5].adj = INFINITY;

pGraphic->arcs[2][2].adj = 0;
pGraphic->arcs[2][3].adj = 50;
pGraphic->arcs[2][4].adj = INFINITY;
pGraphic->arcs[2][5].adj = INFINITY;

pGraphic->arcs[3][3].adj = 0;
pGraphic->arcs[3][4].adj = 20;
pGraphic->arcs[3][5].adj = 10;

pGraphic->arcs[4][4].adj = 0;
pGraphic->arcs[4][5].adj = 60;

pGraphic->arcs[5][5].adj = 0;

for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
pGraphic->arcs[j][i] = pGraphic->arcs[i][j];
}
}

PrintGraphic(pGraphic);

}

//释放图空间
void DestroyGraphic(Graphic **ppGraphic)
{
NULL_PTR_RET(ppGraphic)

if(NULL != *ppGraphic)
{
free(*ppGraphic);
*ppGraphic = NULL;
}

return ;

}

//打印最短路径
void PrintShortestPath(Graphic *pGraphic,PathFinal *path)
{
int v,w;
NULL_PTR_RET(path)
NULL_PTR_RET(pGraphic)

printf("src:vex[%d]\n",path->v0);
for (v=0; v<pGraphic->vexnum; v++)
{
if(path->P[v][0]<INFINITY)
{ //存在最短路径
printf("dest:vex[%d] ：",v);
for (w=0; w<pGraphic->vexnum; w++)
{
if(path->P[v][w]<INFINITY)
{
printf("%d->",path->P[v][w]);
}
}
printf(" shortest[%d]",path->D[v]);
printf("\n");
}
}
}

/********************************************************************

函数名：shortestPath_DIJ

函数功能：迪杰斯特拉求最短路径

P[v]：按坐标顺序记录路径上的顶点编号,表示从v0到v的最短路径（节点集），p[v][w]表示v0到v路径中，第w个顶点的编号。
D[v]：v0-v的最短路径值
final[v]为TRUE，当且仅当v属于S，即已经求得v0到v的最短路径。为FALSE表示v还属于V集，没有找到最短路径。

严蔚敏书算法，如果v0到v有最短路径v0、vi、vj、vk，则P[v][v0]、P[v][vi]、P[v][vj]、P[v][vk]]、P[v][v]为真，按坐标顺序输出路径时只能列出相应顶点，路径顺序不能保证。
修改严算法，可以得到具体的路径。

入参:Graphic *pGraphic,path->v0

出参：PathFinal *path()

返回值：无

*********************************************************************/

void ShortestPath_DIJ(Graphic *pGraphic, PathFinal *path)
{

int v,k,i,w,min,final[MAX_VEX_NUM];

/*合法性判断*/
NULL_PTR_RET(pGraphic)
NULL_PTR_RET(path)

/*初始化阶段begin****************************************/

for (v=0; v<pGraphic->vexnum; v++)
{
final[v]=LX_FALSE;

//权值初始化
path->D[v]=pGraphic->arcs[path->v0][v].adj; // D的初值是v0到其余顶点的直接弧的权值

//路径初始化(设空所有路径)
for(w=0; w<pGraphic->vexnum; w++)
{
path->P[v][w]=INFINITY;
}

//第一次求得的v0到其余顶点的最短路径
if (path->D[v]<INFINITY)
{
path->P[v][0]=path->v0; //v0到v路径的第0个节点为v0
path->P[v][1]=v; //v0到v路径的第1个节点初始化为v(后面还会改)
}
}

path->D[path->v0]=0; //v0到v0当然为0
final[path->v0]=LX_TRUE; //初始化，v0属于S集

/*初始化阶段end****************************************/

/*求最短路径begin****************************************/
v=path->v0; //用v记住最近的顶点,初始化为v0

for (i=1; i<pGraphic->vexnum; i++) //这里循环要从1开始，其余G.vexnum-1个顶点
{

//直达求最短：从V中选取一个其距离值为最小的顶点W且不在S中，加入S
min=INFINITY; //min是当前所知离v0顶点的最近距离
for (w=0; w<pGraphic->vexnum; w++)
{
if (!final[w]) // w顶点在V-S中
{
if (path->D[w]<min)
{
min=path->D[w];
v=w; ////w离v0更近，用v记住最近的顶点
}
}
}
final[v]=LX_TRUE; //找到最短，将v加入S
//说明：直达的最短不一定是最短，还可能是从S中的顶点转达才最短，下面会再次做比较，这里是提前将final标记置为TRUE。

//非直达求最短：对V中顶点的距离值进行修改，若加进W作中间顶点，从V0到V的距离值比不加W的路径要短，则修改此距离值
for (w=0; w< pGraphic->vexnum; w++)
{
if (!final[w] && (min + pGraphic->arcs[v][w].adj < path->D[w]))
{
path->D[w]= min + pGraphic->arcs[v][w].adj;//刷新最短距离

//复制最短路径，此处与严书不同
//初始：p[v]= {v0,....,v,INFINITY,INFINITY,......}
// p[w]= {INFINITY,....,INFINITY,INFINITY,INFINITY,......}
for(k=0; k<pGraphic->vexnum; k++)
{
if(path->P[v][k]<INFINITY)
{
path->P[w][k]=path->P[v][k]; //复制v0-v的路径到v0-w中
//p[w]= {v0,....,v,INFINITY,INFINITY,......}
}
else
{
path->P[w][k]=w;//将w也加入到v0-w中（v到w是直达的）
//p[w]= {v0,....,v,w,INFINITY,INFINITY,......}
break; //这里必须break
}
}
//最终：p[w]= {v0,....,v,w,INFINITY,INFINITY,......}
}
}
}

/*求最短路径end****************************************/
}

//测试程序

Graphic *gpGraphic;
PathFinal gPath;

void TestCaseForGraphic()
{
gpGraphic = CreateGraphic();
SetGraphic(gpGraphic);

gPath.v0 = 5;

//求最短路径
ShortestPath_DIJ(gpGraphic,&gPath);

//打印
PrintShortestPath(gpGraphic,&gPath);

DestroyGraphic(&gpGraphic);
}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 迪杰斯特拉算法求最短距离

迪杰斯特拉算法求最短距离

看完仍有疑问？有类似问题直接问程序猿