解決單源最短路徑問題的一般方法是Dijkstra算法,該算法是貪婪算法的典型應用。其基本思想是對有向賦權圖以開始頂點出發,逐層外擴(即廣度優先搜尋),以尋找目前最短路徑。
1、從頂點V1為出發頂點,其距離dv1=0,為最小值,是以選擇處理v1,将v1設為已知,與V1連接配接的頂點為v2、v4。其距離均小于目前dv4 和dv2的無窮大,是以更新:dv4=1,dv2=2;
2、選擇目前距離最小未知頂點v4,,将v4設為已知。與v4鄰接頂點為v3,v5,v6,v7,更新距離:dv3=1+2=3,dv6=1+8=9,dv7=1+4=5,dv5=1+2=3;(因為新值均小于他們的目前值無窮大,是以需要更新)。
3、選擇目前距離最小未知頂點為v2,将v2設為已知。 與v2連接配接點為v4,但v4已知,是以不需更新。連接配接點v5,由于dv2+10=12>dv5=3,是以不更新dv5。
4、選擇目前距離最小未知頂點v5,設為已知。更新其連接配接點:v7,但因為dv5+6=3+6> dv7=5,是以不用更新。
5、選擇目前距離最小未知頂點v3,設為已知,且更新v6距離dv6=6。
6、最後選擇v6,設為已知。此時所有頂點處理完畢。
實作代碼如下:
/*Dijkstra 算法聲明*/
typedef int Vertex;//頂點
typedef int DistType;
struct List;
/*每個頂點對應一個TaleEntry結構*/
struct TableEntry
{
Lsit Header;//鄰接頂點連結清單
int Know;//表示該頂點是否已經已知(即處理過了)
DistType Dist;//起點到該點的權值距離
Vertex Path;//到達該點的前一頂點
};
/*頂點标号從0開始*/
#define NotAvertex (-1)
#define INF 0x7fffffff
typedef struct TableEntry Table[NumVertex];
/*表初始化*/
void InitTable(Vertex start,Graph G,Table T)
{
int i;
ReadGraph(G,T);//将圖讀入到連接配接表中
for(i=;i<NumVertex;++i)
{
T[i].Know=false;
T[i].Dist=INF;
T[i].Path=NotAvertex;
}
T[start].Dist=;
}
/*遞歸列印到給定頂點的最短路徑*/
void PrintPath(Vertex V,Table T)
{
if(T[V].Path!=NotAvertex)//如果還有前向頂點,則先列印前面的頂點
{
PrintPath(T[V].Path,T);
printf(" to ");
}
printf(" %d ",V);
}
/*Dijkstra 算法*/
void Dijkstra(Table T)
{
Vertex V,W;
for(; ;)
{
V=smallest unknow distance vertex;//取目前未知頂點中的權值最小的頂點
if(V==NotAvertex)
break;
T[V].know=true;
for each W adjacent to V //調整連接配接到V的所有頂點W的距離值
if(!T[W].know) //僅更新未知頂點
{
if(T[W].Dist>T[V].Dist+Cvw)//僅當新的距離值小于目前距離值時才更新它,并同時更新其前向節點
{
T[W].Dist=T[V].Dist+Cvw;
T[w].Path=V;
}
}
}
隻要沒有負值邊,以上算法總能正确完成。
性能分析:
需要注意的是,如果用優先隊列來實作查找最小距離時,每次将更新的dw要更新到原隊列中對應點的d值,但是用二叉堆實作的優先隊列的Find操作低效的。是以可以采取重複插入到優先隊列的辦法,這時隊列中将可能存在一個點的多個版本,是以在每次DeleteMin操作把最小點從隊列删除時,必須檢查以肯定該點是未知的,進而避免對已知點重複處理,如果該點為已知,則丢棄,從新DeleteMin。這種實作方法不會增加時間界,但是會增加空間需求。當然可以選用其他的資料結構實作的優先隊列,比如斐波那契堆等。