有关于Dijkstra算法在物流配送中应用

论文导读：*/{printf（“<--%d”，pre）；pre=P；}if（D！=max&&D！=0）printf（“<--%d＼n”，v）；elseprintf（“＼n”）；}}main（）{MgraphG；inte；inti，j，v；printf（”pleaseinputthenumberoftheedgeinthegraph：”）；scanf（“%d”，&e）；/*输入边数*/creat_Mgraph（&G，e）
【摘要】配送运输是物流系统中最重要的组成部分之一，正是通过配送运输，配送中心才得以最终完成货物从商户到用户的转移。由于配送中心每次配送活动一般都面对多个非固定用户，并且这些用户坐落地点各不相同，所以对于它们的配送路线十分重要。迪杰斯特拉算法是典型最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法能得出物流配送中最短路径的最优解。
【关键词】最短路径算法；物流配送；路径优化
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；ifor （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；iS[v]=1； /*v的访问标志是1*/
D[v]=0； /*v1到v1的路径长度是0*/
for （i=0；i{
min=max；
for （j=0；jif （（！S[j]）&&（D[j]{ min=D[j]； k=j； } /*选出离源点最近的顶点*/
S[k]=1；
for （j=0；jif （（！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；jprintf（"%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 函数*/
} 全文地址：www.7ctime.com/cgygygllw/lw49866.html上一论文：探讨物流企业成本制约信息技术应用