2015年软考程序员考试复习笔试知识点整理（12）-软件水平-计算机-珠峰网 www.my8848.com

2015年软考程序员考试复习笔试知识点整理（12）

发布时间：2011/4/27 16:43:42 来源：城市学习网编辑：ziteng

　　16、单源最短路径

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

　　Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树，先用dist[]数组维护一个最短路径，dist[v]表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时，我们找一条边，x 属于当前最短路径树中的点，y不属于当前最短路径树中的点，使得 dist[x]+ w(x,y) 最小，将边加入到最短路径树中，依次进行，最后求得就是从起点 v0 出发的最短路径。

　　最短路径 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<

　　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;

　　}