$arr_a=array(
1=>array(14418,8046),array(11664,8010),
array(8118,7974),
array(9162,7992),
array(9630,7992),
array(7398,7956),
array(4716,7956),
array(6750,7956),
array(1602,7938),
array(3528,7902),
array(5616,7920),
array(2502,7902),
array(8118,7668),
...
//307个点1-307个点的x y$arr_b=array(
array(1,2),
array(1,35),
array(2,5),
array(2,21),
array(3,6),
array(3,4),
array(3,13),
array(4,5),
array(4,15),
array(5,16),
array(6,8),
array(6,18),
array(7,10),
....//有458个连路
(1,2)表示 1到2点有条线已知 上面数据 现在怎么求 任意两点之间的路线和距离啊!相连两点的距离 (int)sqrt(pow(($a[0]-$b[0]),2)+pow(($a[1]-$b[1]),2));
求用floyd 算法 实现啊 也可以不用 只要实现喔。xxxxxxxxxxxxxxx
floyd 算法 把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i,j]=d,d表示该路的长度;否则G[i,j]=空值。
定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j。
把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j], G[i,k]+G[k,j] ),如果G[i,j]的值变小,则D[i,j]=k。
在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。
有点不大明白floyd 算法 请指教啊!
1=>array(14418,8046),array(11664,8010),
array(8118,7974),
array(9162,7992),
array(9630,7992),
array(7398,7956),
array(4716,7956),
array(6750,7956),
array(1602,7938),
array(3528,7902),
array(5616,7920),
array(2502,7902),
array(8118,7668),
...
//307个点1-307个点的x y$arr_b=array(
array(1,2),
array(1,35),
array(2,5),
array(2,21),
array(3,6),
array(3,4),
array(3,13),
array(4,5),
array(4,15),
array(5,16),
array(6,8),
array(6,18),
array(7,10),
....//有458个连路
(1,2)表示 1到2点有条线已知 上面数据 现在怎么求 任意两点之间的路线和距离啊!相连两点的距离 (int)sqrt(pow(($a[0]-$b[0]),2)+pow(($a[1]-$b[1]),2));
求用floyd 算法 实现啊 也可以不用 只要实现喔。xxxxxxxxxxxxxxx
floyd 算法 把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i,j]=d,d表示该路的长度;否则G[i,j]=空值。
定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j。
把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j], G[i,k]+G[k,j] ),如果G[i,j]的值变小,则D[i,j]=k。
在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。
有点不大明白floyd 算法 请指教啊!
解决方案 »
- discuz安装到最后不出现到后台运行
- php写的api接口如何传递大数据
- apache怎样让http://localhost/pm指向网址http://pm.com
- 问一下大伙,dedecms数据库连接文件怎么配置呀
- 我的网站中无缘无故的多了很多文件夹和文件是怎么回事
- PHP输出uniqueidentifier类型问题【在线等】
- localhost小问题
- phpcms中的 PC标签中的条件为啥是这样的
- 求助:关于libiconv包安装问题,明明已经编译安装成功,但是调用包的时候又找不到
- 问个问题
- touch文件后我又写入内容编码不是格式怎么确定?
- 請問哪位大俠有經典的用php實現驗証碼的功能﹖
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}
这是c++的,很容易转成php,好好认识一下这个算法吧http://baike.baidu.com/view/14495.htm
http://www.zzxj.net/download/source/23
如果字数太多,可以用紧凑格式发
比如
$arr_a=array(
1=>array(14418,8046),array(11664,8010),
array(8118,7974),
array(9162,7992),
array(9630,7992),
array(7398,7956),
array(4716,7956),
....
发为
$arr_a='14418,8046,11664,8010,8118,7974,9162,7992,9630,7992,7398,7956,4716,7956,....
$point = n;//假设N个点
for($i=1;$i<=$point;$i++)
{
for($j=1;$j<=$point;$j++)
{
$dis[$i][$j] = 10000000;//如果两条间没有直线则假设距离为这么大,可以更大
}
}
/××××已知的两点间的直线距离×××××/
$dis[1][2] = 10;
$dis[1][5] = 19;
$dis[1][6] = 21;
$dis[5][6] = 33;
$dis[5][4] = 18;
$dis[6][2] = 11;
$dis[6][4] = 14;
$dis[2][4] = 6;
$dis[2][3] = 5;
$dis[4][3] = 6;$dis[2][1] = 10;
$dis[5][1] = 19;
$dis[6][1] = 21;
$dis[6][5] = 33;
$dis[4][5] = 18;
$dis[2][6] = 11;
$dis[4][6] = 14;
$dis[4][2] = 6;
$dis[3][2] = 5;
$dis[3][4] = 6;
/××××已知的两点间的直线距离×××××/
function Dcount($dis)
{
for($k=1;$k<=$point;$k++)
{
for($i=1;$i<=$point;$i++)
{
for($j=1;$j<=$point;$j++)
{
if(($dis[$i][$k]+$dis[$k][$j]) < $dis[$i][$j])
{
$dis[$i][$j] = $dis[$i][$k]+$dis[$k][$j];
}
}
}
}
return $dis;
}$new_dis = Dcount($dis);
print_r($new_dis);?>