高考问答气血不足吃什么药好呢:关于图的最短路算法
来源：百度文库 编辑：高考问答 时间：2024/04/29 06:02:41
Dijkstra算法是算单源最短路.o(n^2)
Floyd是算任意一对顶点间的最短路.o(n^3)
Floyd算法的描述如下(PASCAL):
short:=cost;{short为最短路数组,cost为图的邻接矩阵}
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if cost[i,j]<cost[i,k]+cost[k,j] then short[i,j]:=short[i,k]+short[k,j]{如果i到k再到j的距离小于i到j的距离,则改变short[i,j]}
请问:如果将for i:=1 to n do一行去掉,给i赋一个定值,那此时Floyd算法是否可以算出结点i到任意接点的单源最短路径?(如果可以,写起来倒比Dijkstra算法简单多了)
Floyd是算任意一对顶点间的最短路.o(n^3)
Floyd算法的描述如下(PASCAL):
short:=cost;{short为最短路数组,cost为图的邻接矩阵}
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if cost[i,j]<cost[i,k]+cost[k,j] then short[i,j]:=short[i,k]+short[k,j]{如果i到k再到j的距离小于i到j的距离,则改变short[i,j]}
请问:如果将for i:=1 to n do一行去掉,给i赋一个定值,那此时Floyd算法是否可以算出结点i到任意接点的单源最短路径?(如果可以,写起来倒比Dijkstra算法简单多了)
可以算出任意一个确定顶点到任意节点的单源最短路径.
要证明么?好像不太说的清楚....
写起来也确实比Dijkstra算法简单,而且是很标准的o(n^2),
但显然是Dijkstra算法的效率稍微高一些.....