Dijkstra算法在物流配送中的应用研究

杨刘翔

【摘要】配送运输是物流系统中最重要的组成部分之一，正是通过配送运输，配送中心才得以最终完成货物从商户到用户的转移。由于配送中心每次配送活动一般都面对多个非固定用户，并且这些用户坐落地点各不相同，所以对于它们的配送路线十分重要。迪杰斯特拉算法是典型最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法能得出物流配送中最短路径的最优解。

【关键词】最短路径算法；物流配送；路径优化

1.前言

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：

a.Dijkstra算法；

b.A*算法；

c.Bellman-Ford算法；

d.Floyd-Warshall算法；

e.Johnson算法；

2.Dijkstra算法

算法的基本思想：

（1）先设一个辅助量D，他的分量D[i]表示从起始点v到终点vi的最短路径的长度。若v到vi有弧，则D[i]为弧上的权值；否则D[i]为。

所以为从v出发的一条最短路径。此路径为（v，vj）。

（2）下一条长度次短的最短路径：假设其终点为vk，则路径为（v，vk）或（v，vj，vk）。他的长度或者是从v到vk的权值或者是D[j]和从vj到vk的权值的和。所以，可以假设S为已求得的最短路径的终点的集合，在一般情况下，下一条长度次短的最短路径的长度为：

3.Dijkstra算法的具体应用

/* 建立有向图的邻接矩阵存储结构，并求出给定源点到其余各点的最短路径*/

#include

#define VEX_NUM 8 /*顶点数目*/

#define MAX 999 /*较大的权值*/

typedef char Vextype； /*顶点类型*/

typedef struct

{ Vextype vexs[VEX_NUM]； /*顶点表*/

int arcs[VEX_NUM][VEX_NUM]； /*邻接矩阵，表示边的权值*/

}Mgraph；

/*建立有向图的邻接矩阵G ，e为边的数目*/

void creat_Mgraph（ Mgraph *G，int e）

{ int i，j，k，w；

printf（"please input the vex of the graph：＼n"）；

scanf（“%s”，G->vexs）； /*输入顶点信息*/

for （i=0；i

for （j=0；j

/*将邻接矩阵中的边标记上一个较大的值，但是对角线上标注0*/

if（i==j） G->arcs[i][j]=0；

else G->arcs[i][j]=MAX；

for（k=0；k

{

scanf（“%d-%d，%d”，&i，&j，&w）； /*输入表示边（vi，vj）的顶点序号i，j*/

G->arcs[i][j]=w；

}

}

DIJKSTRA（Mgraph *G， int v） /*从v到其它顶点的最短路径*/

{

int D[VEX_NUM]； /*存放从源点到顶点的路径长度*/

int P[VEX_NUM]，S[VEX_NUM]；

/*p存放的是从源点到目标点路径上的顶点，s是访问标志*/

int i，j，k，pre；

int min，max=MAX；

for （i=0；i

{

D[i]=G->arcs[v][i]；

if （D[i]！=max） P[i]=v；

else P[i]=-1；

}

for （i=0；i

S[v]=1； /*v的访问标志是1*/

D[v]=0； /*v1到v1的路径长度是0*/

for （i=0；i

{

min=max；

for （j=0；j

if （（！S[j]）&&（D[j]

{ min=D[j]； k=j； } /*选出离源点最近的顶点*/

S[k]=1；

for （j=0；j

if （（！S[j]）&&（D[j]>D[k]+G->arcs[k][j]））

{

D[j]=D[k]+G->arcs[k][j]；

P[j]=k；

}

}

for （i=0；i

{

printf（“%d，%d”，D[i]，i）；

pre=P[i]；

while （pre！=-1 && pre！=v） /*-1表示到源点没有路径，v表示路径已经到源点了*/

{

printf（“<--%d”，pre）；

pre=P[pre]；

}

if（D[i]！=max && D[i]！=0） printf（“<--%d＼n”，v）；

else printf（“＼n”）；

}

}

main（）

{

Mgraph G；

int e；

int i，j，v；

printf（”please input the number of the edge in the graph：”）；

scanf（“%d”，&e）；/*输入边数*/

creat_Mgraph（&G，e）；/*调用creat_Mgraph 函数*/

for（i=0；i

{

for（j=0；j

printf（"%8d"，G.arcs[i][j]）；

printf（"＼n"）；

}

printf（"please input the yuandian：＼n"）；

scanf（“%d”，&v）；/*輸入源点*/

printf（"the shortest path is：＼n "）；

DIJKSTRA（&G， v）；/*调用DIJKSTRA 函数*/

}