2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(12)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識點整理匯總

　　16、單源最短路徑

　　(1)Dijkstra 算法可以用來解決非負(fù)權(quán)重網(wǎng)絡(luò)的單源點最短路徑。

　　Dijkstra 算法的基本思想就是用貪心策略維護(hù)一棵最短路徑生成樹，先用dist[]數(shù)組維護(hù)一個最短路徑，dist[v]表示起點 v0 與當(dāng)前最短路徑樹中的頂點 v 的最短路徑。選擇下一個頂點時，我們找一條邊 ，x 屬于當(dāng)前最短路徑樹中的點，y不屬于當(dāng)前最短路徑樹中的點，使得 dist[x]+ w(x,y) 最小，將邊 加入到最短路徑樹中，依次進(jìn)行，最后求得就是從起點 v0 出發(fā)的最短路徑。

　　最短路徑 dijsktra 算法模板：

　　#include

　　usingnamespace std;

　　constint maxint = 9999999;

　　constint maxn = 1010;

　　intdata[maxn][maxn];//data存放點點之間的距離，

　　intlowcost[maxn]; //lowcost存放點到start的距離, 從0開始存放

　　boolused[maxn];//標(biāo)記點是否被選中

　　intn; //頂點的個數(shù)

　　voiddijkstra(int start)//初始點是start的dij算法

　　{

　　int i,j;

　　memset(used, 0, sizeof(used));

　　//init

　　for(i = 0; i < n; i++)

　　lowcost[i] = data[start][i];

　　used[start] = true;

　　lowcost[start] = 0;

　　for(i = 0; i < n-1; i++)

　　{

　　//choose min

　　int tempmin = maxint;

　　int choose;

　　for(j = 0; j < n; j++)

　　{

　　if(!used[j] && tempmin >lowcost[j])

　　{

　　choose = j;

　　tempmin = lowcost[j];

　　}

　　}

　　used[choose] = true;

　　//updata others

　　for(j = 0; j < n; j++)

　　{

　　if(!used[j] &&data[choose][j] < maxint && lowcost[choose]+data[choose][j]

　　{

　　lowcost[j] =lowcost[choose]+data[choose][j];

　　}

　　}

　　}

　　}

　　intmain()

　　{

　　int start , i , j;

　　cin>>n;

　　for(i = 0; i < n; i++)

　　for(j = 0; j < n; j++)//輸入頂點信息

　　{

　　cin>>data[i][j];

　　}

　　cin>>start;

　　dijkstra(start);

　　int min = 0;

　　for(i = 0; i < n; i++)

　　{

　　cout<

　　for(i=0;i

　　{

　　for(j=0;j

　　a[i][j]=MAX;

　　for(i=0;i

　　a[i][i]=0;

　　while(edge_amount--)

　　{

　　scanf("%d%d%d",&i,&j,&w);

　　a[i][j]=w;

　　}

　　Bellman_Ford(0);

　　for(i=0;i

　　{

　　printf("dist:%d\t",d[i]);

　　printf("path: %d",P[i]);

　　printf("\n");

　　}

　　}

　　return 0;

　　}

　　軟考程序員考試歷年真題重點題總結(jié)及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)