Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Floyd

Posted on 2009-08-28 09:13 reiks 阅读(148) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构
#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;
}

/*
注解:无法连通的两个点之间距离为0;
Sample Input
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 70
00 70 50 00 10 00 50
00 00 00 00 70 50 00
*/

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理