关于Floyd的打印路径的个人总结

如图这个最短路

很明显要打印该条路的路径，需要这条路上的各个节点都能被枚举到，最简单的方式就是path[1][8]=5,path[5][8]=4,path[4][8]=7,path[7][8]=8;显然如果要满足以上的要求,当map[i][j]时path[i][j]=path[i][k]即可.

举例:

k=4 时

path[5][7]=path[5][4]=4

k=7 时

path[5][8]=path[5][7]=4

所以path[5][8]=4满足以上条件

代码实现:

初始化:

	for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				path[i][j]=j;
				
			}
		}

实现:

	for(k=1;k<=n;k++)
		{
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
				{
					if(map[i][j]>map[i][k]+map[k][j]+tax[k])
					{
						path[i][j]=path[i][k];
						map[i][j]=map[i][k]+map[k][j]+tax[k];
					}
					if(map[i][j]==map[i][k]+map[k][j]+tax[k])
					{
						path[i][j]=min(path[i][j],path[i][k]);
					}
				}	
			}	
		}