算法流程：

(a)?初始化：用起點v到該頂點w的直接邊(弧)初始化最短路徑，否則設為∞；

(b)?從未求得最短路徑的終點中選擇路徑長度最小的終點u：即求得v到u的最短路徑；

(c)?修改最短路徑：計算u的鄰接點的最短路徑，若(v,…,u)+(u,w)<(v,…,w)，則以(v,…,u,w)代替。同時，用path記錄每個節點最短路徑的前導節點。

(d)?重復(b)-(c)，直到求得v到其余所有頂點的最短路徑。

一共有N個節點，出發結點為V0，需要一個一維數組path[N]來記錄前一個節點序號，一個一維數組dist[N]來記錄從原點到當前節點最短路徑（初始值為V0到Vi的邊的權值，沒有則為+∞，這里用MAX=65536來代替無窮大），一個二維數組cost[N][N]來記錄各點之間邊的權重，按以上流程更新path[N]和dist[N]。

測試：

測試用例用的是課件的例子，總共有7個節點，打印從節點1到別的節點的最短路徑。

輸出路徑，主要用遞歸輸出，printpath打印每個節點的前面的節點，直至到第一個節點。

#include <iostream>using namespace std; //點的個數大小 #define N 7 //用MAX表示無窮大 #define MAX 65536/* G是一個N結點有向圖，它由其成本鄰接矩陣cost(n,n)表示DIST(j)被置 以結點v到結點j的最短路徑長度，這里1≤j≤n。DIST(v)被置成零,path 用于記錄路徑 */ void SHORTEST_PATHS(int v,int cost[N][N],int dist[N],int path[6],int n) {//visit數組，記錄訪問過的節點，訪問過置為1，否則置為0//初始化全為0int visit[N] = {0};for(int i=0;i<N;++i){//別的點到V0點的初始化距離dist[i] = cost[0][i];//path數組用于記錄路徑，記錄前面的節點if(dist[i] != MAX)path[i] = 0;}//將V0點置為1表示訪問過visit[0] = 1;dist[0] = 0;for(int i=1;i<N;++i){int u;int temp = MAX;for(int j=0;j<N;++j){if(visit[j]==0 && dist[j]<temp){//u用來記錄下一個被選入集合S的點u = j;temp = dist[j];}}visit[u] = 1;//更新所有點的距離for(int j=0;j<N;++j){if(visit[j] == 0){//如果加入的點使得距離變小了，就更新int newdist = dist[u]+cost[u][j];if(newdist < dist[j]){dist[j] = newdist;path[j] = u;}}}} } //遞歸打印路徑 void printpath(int path[],int end) {if(end == 0)return;printpath(path,path[end]);printf("V%d",path[end]); }int main() {//測試用例，來自課件int cost[N][N] = {{0,20,50,30,MAX,MAX,MAX},{MAX,0,25,MAX,MAX,70,MAX},{MAX,MAX,0,40,25,50,MAX},{MAX,MAX,MAX,0,55,MAX,MAX},{MAX,MAX,MAX,MAX,0,10,70},{MAX,MAX,MAX,MAX,MAX,0,50},{MAX,MAX,MAX,MAX,MAX,MAX,0},};int dist[N];int path[N];SHORTEST_PATHS(0,cost,dist,path,N);cout<<"start\tend\tlength\tnodes list"<<endl;//格式化輸出for(int i=1;i<N;++i){cout<<"V0\tV"<<i<<"\t"<<dist[i]<<"\t";printpath(path,i);cout<<"V"<<i<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的贪心算法-单源最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。