Dijkstra算法在物流配送中的應(yīng)用研究

楊劉翔

【摘要】配送運輸是物流系統(tǒng)中最重要的組成部分之一，正是通過配送運輸，配送中心才得以最終完成貨物從商戶到用戶的轉(zhuǎn)移。由于配送中心每次配送活動一般都面對多個非固定用戶，并且這些用戶坐落地點各不相同，所以對于它們的配送路線十分重要。迪杰斯特拉算法是典型最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。算法能得出物流配送中最短路徑的最優(yōu)解。

【關(guān)鍵詞】最短路徑算法；物流配送；路徑優(yōu)化

1.前言

用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：

a.Dijkstra算法；

b.A*算法；

c.Bellman-Ford算法；

d.Floyd-Warshall算法；

e.Johnson算法；

2.Dijkstra算法

算法的基本思想：

（1）先設(shè)一個輔助量D，他的分量D[i]表示從起始點v到終點vi的最短路徑的長度。若v到vi有弧，則D[i]為弧上的權(quán)值；否則D[i]為。

所以為從v出發(fā)的一條最短路徑。此路徑為（v，vj）。

（2）下一條長度次短的最短路徑：假設(shè)其終點為vk，則路徑為（v，vk）或（v，vj，vk）。他的長度或者是從v到vk的權(quán)值或者是D[j]和從vj到vk的權(quán)值的和。所以，可以假設(shè)S為已求得的最短路徑的終點的集合，在一般情況下，下一條長度次短的最短路徑的長度為：

3.Dijkstra算法的具體應(yīng)用

/* 建立有向圖的鄰接矩陣存儲結(jié)構(gòu)，并求出給定源點到其余各點的最短路徑*/

#include

#define VEX_NUM 8 /*頂點數(shù)目*/

#define MAX 999 /*較大的權(quán)值*/

typedef char Vextype； /*頂點類型*/

typedef struct

{ Vextype vexs[VEX_NUM]； /*頂點表*/

int arcs[VEX_NUM][VEX_NUM]； /*鄰接矩陣，表示邊的權(quán)值*/

}Mgraph；

/*建立有向圖的鄰接矩陣G ，e為邊的數(shù)目*/

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

/*將鄰接矩陣中的邊標(biāo)記上一個較大的值，但是對角線上標(biāo)注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存放的是從源點到目標(biāo)點路徑上的頂點，s是訪問標(biāo)志*/

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的訪問標(biāo)志是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表示路徑已經(jīng)到源點了*/

{

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）；/*輸入邊數(shù)*/

creat_Mgraph（&G，e）；/*調(diào)用creat_Mgraph 函數(shù)*/

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）；/*調(diào)用DIJKSTRA 函數(shù)*/

}