杨刘翔

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

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

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）； /*输入顶点信息*/