数据结构最短距离问题

显示全部楼层 · 2011-3-13 12:52:32

问题描述：
给定n个村庄之间的交通图，若村庄 i 和村庄 j 之间有道路，则将顶点 i 和顶点 j 用边连接，边上的权 Wij 表示这条道路的长度。现在要从这 n 个村庄选择一个村庄建一所学校，问这所学校应建在哪个村庄，才能使离学校最远的村庄到学校的距离最短？试编程解决该问题。

千问 · 2011-3-13 12:52:32

<pre id=\"best-answer-content\" class=\"reply-text mb10\">这个是Floyd 算法的多点间的最短距离求解问题你把Floyd 算法写下就可以
void floyd(){
int path[][]=new int[n][n];
int dist[][]=new int[n][n];
for(int i=0;in;i)

for(int j=0;jnj){

dist[j]=costValue[j];

if(i!=j FrameMain,MAXNUM)

path[j]=i;

else

path[j]=0;
}

for(int k=0;kn;k)

for(int i=0;in;i)

for(int i=0;jn;j)
if( dist[k] dist[k][j]dist[j] ){

dist[j]= dist[k] dist[k][j];

path[j]=path[k][j];
}
}

数据结构 最短距离问题

数据结构最短距离问题