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

楊劉翔

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

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

1.前言

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

a.Dijkstra算法；

b.A*算法；

c.Bellman-Ford算法；

d.Floyd-Warshall算法；

e.Johnson算法；

2.Dijkstra算法

算法的基本思想：

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

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

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

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

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

#include

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

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

typedef char Vextype； /*頂點(diǎn)類型*/

typedef struct

{ Vextype vexs[VEX_NUM]； /*頂點(diǎn)表*/

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）； /*輸入頂點(diǎn)信息*/

for （i=0；i

for （j=0；j

/*將鄰接矩陣中的邊標(biāo)記上一個(gè)較大的值，但是對角線上標(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）的頂點(diǎn)序號i，j*/

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

}

}

DIJKSTRA（Mgraph *G， int v） /*從v到其它頂點(diǎn)的最短路徑*/

{

int D[VEX_NUM]； /*存放從源點(diǎn)到頂點(diǎn)的路徑長度*/

int P[VEX_NUM]，S[VEX_NUM]；

/*p存放的是從源點(diǎn)到目標(biāo)點(diǎn)路徑上的頂點(diǎn)，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； } /*選出離源點(diǎn)最近的頂點(diǎn)*/

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表示到源點(diǎn)沒有路徑，v表示路徑已經(jīng)到源點(diǎn)了*/

{

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）；/*輸入源點(diǎn)*/

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

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

}