紙上談兵 最短路徑與貪婪

1、圖是由節(jié)點和連接節(jié)點的邊構(gòu)成的。節(jié)點之間可以由路徑，即邊的序列。根據(jù) 路徑，可以從一點到達另一點。在一個復(fù)雜的圖中，圖中兩點可以存在許多路 徑。最短路徑討論了一個非常簡單的圖論問題，圖中從A點到B點，那條路 徑耗費最短？這個問題又異常復(fù)雜，因為網(wǎng)絡(luò)的構(gòu)成狀況可能很復(fù)雜。一個最簡單的思路，是找出所有可能的從A到B的路徑，再通過比擬，來尋找最短路徑。然而，這并沒有將問題簡化多少。因為搜索從A到B的路徑,這本 身就是很復(fù)雜的事情。而我們在搜索所有路徑的過程中,有許多路徑已經(jīng)繞了狀態(tài)距離A0C1D鄰接6E鄰接9P鄰接4第二步狀態(tài)距離A0C1D鄰接6E鄰接7狀態(tài)距離P4第三步狀態(tài)距離A0C1D6E鄰接7

2、P4最后，E成為。倒退，可以知道路徑為E, P, C, Ao正過來，就是從A到E 的最短路徑了。上面的算法是經(jīng)典的Dijkstra算法。本質(zhì)上，每個鄰接點記錄的，是基于 點的情況下,最好的選擇，也就是所謂的“貪婪算法(greedy algorithm)o 當(dāng)我們貪婪時，我們的決定是臨時的，并沒有做出最終的決定。轉(zhuǎn)換某個點成 為點后，我們增加了新的可能性，貪婪再次起作用。根據(jù)比照。隨后，某 個鄰接點成為新的貪無可貪”的點，即經(jīng)由其它任意鄰接點，到達該點都只 會造成更高的本錢；經(jīng)由未知點到達該點更不可能，因為未知點還沒有開放, 必然需要經(jīng)過現(xiàn)有的鄰接點到達，只會更加繞遠。好吧，該點再也沒有貪婪的

3、動力，就被扔到“成功人士”里，成為點。成功學(xué)不斷傳染，最后感染到 目標(biāo)節(jié)點B ,我們就找到了 B的最短路徑。實現(xiàn)理解了上面的原理，算法的實現(xiàn)是小菜一碟。我們借用圖（graph）中的數(shù)據(jù)結(jié) 構(gòu)，略微修改，構(gòu)建加權(quán)圖。我們將上面的表格做成數(shù)組records ,用于記錄路徑探索的信息。重新給點A,C,D,E,P命名，為A 1, 2, 3, 40代碼如下：/* By Vamei */ftinclude ftinclude ftdefine NUM_V 5ttdefine INFINITY 10000typedef struct node position;typedef struct record *

4、label;/* node */struct node int element;position next;int weight;);/* table element, keep record */struct record int status;int distance;int previous;/* operations (stereotype)*/void insert_edge(position, int, int, int);void print_ graph(position, int);int new neighbors(position, label, int, int);vo

5、id shortest_path(position, label, int, int, int);/* for testing purpose */void main()(struct node graphNUM_V;struct record recordsNUM_V;int i;/ initialize the verticesfor(i=0; ielement = i;(graph+i)-next = NULL;(graph+i)-weight =-1;/ insert edgesinsert_edge(graph,0,1,1);insertedge(graph,0,2,6);inser

6、t_edge(graph, 0, 3, 9);insert edge (graph, 1, 4, 3);insert_edge(graph, 4, 3, 3);print_graph(graph, NUM_V);/ initialize the bookfor (i=0; istatus =-1;(records+i)-distance = INFINITY;(records+i)-previous =-1;shortest_path(graph, records, NUM_V, 0, 3);/)void shortest_path(position graph, label records,

7、 int nv, int start, int end) int current;(records+start)-status二 1；(records+start)-distance = 0;(records+start)-previous = 0;current = start;while(current != end) current = newneighbors(graph, records, nv, current);while (current != start) printf (，z%d一 ，current);current = (records+current)-previous

8、;printf (z，%dn，z, current);)int newneighbors(position graph, label records, int nv, int current) int newDist;int v;int i;int d;position p;/ update the current known(records + current)-status = 1;/ UPDATE new neighborsp 二(graph+current)-next;while(p !二 NULL) v = p-element;(records + v)-status = 0;new

9、Dist = p-weight + (records + current)-distance; if (records + v)-distance newDist) (records + v)-distance = newDist;(records + v)-previous = current;p = p-next;/ find the next knownd = INFINITY;for (i=0; istatus=0 & (records + i)-distance d) d 二(records + i)-distance;v = i;)return v;/* print the gra

10、ph */void print_graph(position graph, int nv) int i;position p;for (i=0; inext;printfCFrom %3d: ，i);while(p != NULL) printf (，z%d-%d; w:%d ，i, p-element, p-weight);p = p-next;printf (n);)/*insert an edgewith weight*/void insert_edge(position graph, int from, int to, int weight) (position np;position

11、 nodeAddr;np 二 graph + from;nodeAddr =(position) malloc(sizeof(struct node);nodeAddr-element = to;nodeAddr-next = np-next;nodeAddr-we i ght = weight;np-next = nodeAddr;運行結(jié)果如下：From 0: 0-3; w:9 0-2; w:6 0-l; w:lFrom 1: l-4; w:3From 2:From 3:From 4: 4-3; w:33 - 4 - 1 C-D-B ,因為它的總耗費只有4。按照上面的方 法，我們先將A放入記

12、錄。從A出發(fā)，有B和C兩個如果將B和C同時放入 記錄，那么記錄中的B并不符合最短距離的要求。那么，為什么無權(quán)網(wǎng)絡(luò)可行呢？假設(shè)某次記錄時，鞭子長度為5 ,那么這次記錄點的鄰接點，必然是距離為6的點。如果這些鄰接點沒有出現(xiàn)過，那么6就 是它們的最短距離。所有第一次出現(xiàn)的鄰接點，都將加入到下次的記錄中。比 如下面的例子，C/D/E是到達A的鄰接點，它們到A的最短距離必然都是L對于加權(quán)網(wǎng)絡(luò)來說，即使知道了鄰接點，也無法判斷它們是否符合最短距離。 在記錄C/D/E時，我們無法判斷未來是否存在如下列圖虛線的連接,導(dǎo)致a的鄰 接點E并不是下一步的最短距離點：但情況并沒有我們想的那么糟糕。仔細觀察，我們發(fā)現(xiàn)，

13、雖然無法一次判定所 有的鄰接點為下一步的最短距離點，但我們可以確定點C已經(jīng)處在從A出發(fā)的最短距離狀態(tài)。A到C的其它可能性，比方途徑D和E ,必然導(dǎo)致更大的成 本。也就是說，鄰接點中，有一個到達了最短距離點，即鄰接點中，到達A距離最 短的點，比方上面的Co我們可以平安的把C改為點。A和C都是點，點P成為新的鄰接點。P到A得距離為4O出于上面的觀察，我們可以將節(jié)點分為三種：點：到達A最短距離的點。我是成功人士。鄰接點：有從記錄點出發(fā)的邊，直接相鄰的點?！焙统晒θ耸拷?觸，也有成功的機會哦。未知點：還早得很。最初的點只有Ao點的直接下游節(jié)點為鄰接點。對于鄰接點，我們需 要獨立的記錄它們。我們要記錄的有：當(dāng)前情況下，從A點出發(fā)到達該鄰接點的最短距離。比方對于上 面的點D ,為6。此最短距離下的上游節(jié)點。對于上面的點D來說，為Ao每次，我們將鄰接點中最短距離最小的點X轉(zhuǎn)為點，并將該點的直接下游 節(jié)點，改為鄰接點。我們需要計算從A出