1910072盧富毓插點問題

1、云南大學數(shù)學與統(tǒng)計學院 實 驗 報 告課程名稱：算法圖論實驗學期：20132014學年上學期成績：指導教師：李建平姓名：盧富毓學號：20101910072實驗名稱：插值點問題實驗要求：必做實驗學時：2學時實驗編號：02實驗日期：2013-10-10完成日期：2013-10-21學院：數(shù)學與統(tǒng)計學院專業(yè) ：信息與計算科學年級：2010級 一、實驗目的利用dijskra算法實現(xiàn)路的插點問題，掌握如何尋找最短路集合的方法二、實驗環(huán)境vs2010(c+)三、實驗內(nèi)容最短路的插點問題：給定一個連通賦權圖g=（v,e;w.c;s.t）以及正整數(shù)d,這里w,c:e-r+s和t 是兩個固定的頂點，找到s 到

2、t 的最短路集合構(gòu)造一個新的輔助圖，然后修改權值，再次調(diào)用dijskra算法尋求最短路。4、 實驗過程a、插值算法具體描述如下：s和t 是兩個固定的頂點，在圖g中尋找一條從s到t的路ps,t，使得路ps,t的權重w(ps,t)不超過常數(shù)b，并向路ps,t的一些特殊邊上插入一些頂點，不妨設得到的新路為p*s,t,使得新路中任意邊的權重都不超過常數(shù)的d,目標是在滿足上述條件情況下，求出插入頂點后所產(chǎn)生的費用達到最小.即實現(xiàn),這里insert(e)表示加入到邊e中新點的個數(shù)。dijskra算法即標號法，在上學期學過，這里就不作贅述。b、算法運行結(jié)果如下：/圖的輸入/圖的創(chuàng)建以及插值點的限制/最后插值

3、點的結(jié)果五、實驗總結(jié)通過編程，對尋找最短路徑的dijkstra算法也體會更深；復習了求最短路的算法，思考了反圈算法在其中的一些應用。六、源代碼#include#include#include#includeusing namespace std;#define max_vex 100#define m 1000/settextc1是原來的顏色/settextc2 是設置的輸出輸入顏色#define settextc1 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground

4、_red | foreground_green |foreground_blue)#define settextc2 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_green)#define settextc3 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_green | foreground_blue)#define sette

5、xtc4 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red)#define settextc5 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue)#define settextc6 setconsoletextattribute(getstdhandle(std_output_handl

6、e),foreground_red | foreground_green |foreground_blue)#define settextc7 setconsoletextattribute(getstdhandle(std_output_handle),foreground_green)double dmax_vex;/最短路徑p帶權長度和dbool pmax_vexmax_vex;/最短路徑pstring vex,vex2;int v0,v1;class arcllpublic:double weight; /權重;class graphics /創(chuàng)建一個圖的類private:int ve

7、xnum; /頂點數(shù)int arcnum; /邊數(shù)string vexsmax_vex; /存儲定點名稱arcll arcsmax_vexmax_vex; /邊數(shù)double d;/邊的限制public:void creategraphics(graphics &g);/創(chuàng)建一個圖int locateindex(graphics g, string v); / 尋找下標void dijkstra(graphics &g);void insertpoint(graphics &g);/找到相應頂點的下標int graphics:locateindex(graphics g, string v)i

8、nt i=0;for(i=0; ig.vexnum; i+)if(g.pare(v) = 0)return i;return -1;/創(chuàng)建一個圖void graphics:creategraphics(graphics &g)int i,j,k;string vi,vj;double w; /權值settextc1;cout-創(chuàng)建有向圖的存儲-endl;coutg.vexnum;settextc1;/設置顏色coutg.arcnum;settextc1;cout請輸入頂點名:;settextc4;for(i=0; ig.vexsi;settextc1;for(i=0; ig.

9、vexnum; i+) /初始化邊f(xié)or(j=0; jg.vexnum; j+)g.arcsij.weight = m;for(k=0; kg.arcnum; k+)cout請輸入第k+1vivjw;settextc1;i = locateindex(g,vi);j = locateindex(g,vj);if(i = -1 | j = -1)cout輸入錯誤！請檢查.endl;return;g.arcsij.weight = w;g.arcsji.weight = w;coutendl;cout各頂點的關系：endl;settextc2;for(i=0; ig.vexnum; i+) if(

10、i=0)coutttg.vexsi ;else couttg.vexsi ;coutendl;settextc3;for(i=0; ig.vexnum; i+) /初始化邊settextc2;couttg.vexsi ;settextc3;for(j=0; jg.vexnum; j+)if(g.arcsij.weight = m)settextc6;couttm ;settextc3; else couttg.arcsij.weight ;coutendl;settextc1;coutendl圖創(chuàng)建完畢！endl;coutvex;coutendlvex2;coutendlg.d;/*-dijk

11、stra算法-*/void graphics:dijkstra(graphics &g)/bool pmax_vexmax_vex;/最短路徑pbool finalmax_vex;/控制變量int i,j,v,w;double min;cout-v0到v1的最短路徑-endl;v0 = locateindex(g,vex);v1 = locateindex(g,vex2);if(v0 = -1 | v1= -1)cout輸入錯誤！請檢查.endl;return;for(v = 0; v g.vexnum; v+ ) /初始化finalv = false;dv = g.arcsv0v.weigh

12、t;for(w = 0; w g.vexnum; w+)pvw = false;if(dv m)pvv0 = true;pvv = true;dv0 = 0;finalv0 = true;for(i = 1; i g.vexnum; +i)min = m;for(w = 0; w g.vexnum; +w)if(!finalw)if(dwmin)v = w;min = dw; finalv = true;for(w = 0; w g.vexnum; +w)if(!finalw & (min + g.arcsvw.weight dw)dw = min + g.arcsvw.weight;for(

13、j = 0; jg.vexnum; +j)pwj = pvj;pww = true;if(dv1=m)cout不連通！最短路不存在！endl;elsecout從g.vexsv0到g.vexsv1的最短路長度：;coutdv1endl;/*-路的插值算法-*/void graphics:insertpoint(graphics &g)int i,j;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)if(i=j)continue;elseif(g.arcsij.weight+di=dj)g.arcsij.weight = ceil(g.arcsij.weight

14、/g.d)-1;elseg.arcsij.weight=m;coutendl;settextc2;for(i=0; ig.vexnum; i+) if(i=0)coutttg.vexsi ; else couttg.vexsi ;coutendl;for(i=0; ig.vexnum; i+)settextc2;couttg.vexsi ;settextc3;for(j=0; jg.vexnum; j+)if(g.arcsij.weight = m)if(g.arcsji.weight!= m)g.arcsij.weight = g.arcsji.weight;couttg.arcsij.weight ; else settextc6;couttm ;settextc3; else couttg.arcsij.weight ;coutendl;settextc6;g.dijkstra(g);/構(gòu)造新的權值后，再尋找最短路cout最短路：;for(j=0;