$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.   

    #include<fstream>
      #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
      

  2.   

    看看这个吧
    http://www.zzxj.net/download/source/23
      

  3.   

    为了便于测试,请你把两个数组发全。这样也便于交流
    如果字数太多,可以用紧凑格式发
    比如
    $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,.... 
      

  4.   

    <?php
    $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);?>