null三、经典问题 最短路径问题三、经典问题 最短路径问题 null求最短路径的基本思想: 按照最短路径的长度递增的次序依次求得源点到其余各点的最短路径。null 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 路径长度最短的最短路径的特点：假设，从源点到顶点V1的最短路径是所有最短路径中长度最短者。null路径长度次短的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；
或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。null路径长度第三短的路径特点: 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。null其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。null迪杰斯特拉算法：0）准备工作：
设置辅助数组Dist，其中每个分量Dist[k] 表示：当前所求得的从源点到其余各顶点 k 的最短路径。null1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。2）修改其它各顶点的Dist[k]值。
(为什么？)2）修改其它各顶点的Dist[k]值。
(为什么？)具体操作：假设求得最短路径的顶点为u，若 Dist[u]+G.arcs[u][k]
#include
#define INFINITY 0x7fffffff
int g[110][110];
int n,m;
int final[110];//标识结点有没有访问过
int d[110];//最短路存储
void dijkstra(int s)
{
int min,w,v,i;
memset(final,0,sizeof(final));
for(v=1;v<=n;v++)
d[v]=g[s][v];
final[s]=1;
d[s]=0;
for(i=2;i<=n;i++)
{
min=INFINITY;
for(w=1;w<=n;w++)//在所有末标识的点中，选D值最小的点
{
if(!final[w]&&d[w]
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
写错了
{
if(d[w]>min+g[v][w])
d[w]=min+g[v][w];
}
}
printf("%d\n",d[n]);
}
int main()
{
int i,j,x,y,time;
while(scanf("%d%d",&n,&m)&&(m||n))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=INFINITY;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&time);
g[x][y]=g[y][x]=time;
}
dijkstra(1);
}
return 0;
}
浙公网安备 33021202002483