2011年软考程序员考试复习笔试知识点整理(12)

 　16、单源最短路径

　　(1)Dijkstra 算法可以用来解决非负权重网络的单源点最短路径。

　　Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树，先用dist[]数组维护一个最短路径，dist[v]表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时，我们找一条边 

　　最短路径 dijsktra 算法模板：

　　#include

　　usingnamespace std;

　　constint maxint = 9999999;

　　constint maxn = 1010;

　　intdata[maxn][maxn];//data存放点点之间的距离，

　　intlowcost[maxn]; //lowcost存放点到start的距离, 从0开始存放

　　boolused[maxn];//标记点是否被选中

　　intn; //顶点的个数

　　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