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;
}