FLOYD

红太狼 2022-08-05 05:08 169阅读 0赞

求出图中两顶点间的最短路径，让我们想到的是DIJIKSTRA算法，即单源最短路径的算法。那如果求所有顶点两两之间的最短路径的值，是否只要调用N次DIJIKSTRA了？当然可以，其时间复杂度为O（N3），然而这样做，你会发现代码还是比较复杂的。
    这时，用佛罗伊德算法，是比较好的，当然他的时间复杂度也为O(N3).空间复杂度为O(N2)。
    不过，有意思的是，佛罗伊德算法其实是基于动态规划的！这一点自行百度。。不写了
    实现比较简单，我用的是邻接多重表存储的图。(http://blog.csdn.net/qingfengpapa/article/details/46397869)
    **还有一个记录最短路劲的问题，可以用一个PATH[i][j]的数组记录i->j的路劲中，J的前一节点。具体可看代码**

void floyd()
            {
                int i;
                int j;
    
                for(i = 0;i <= this->n;i++)
                {
                    for(j = 0;j <= this->n;j++)
                    {
                        dist[i][j] = MAX_INT;
                        path[i][j] = -1;
                    }
                }
    
                Ebox<T>*p;
                Mark_unvisited();
                for(i = 0;i < this->n;i++)
                {
                    p = adjlist[i].First_edge;
                    while(p)
                    {
                            if(p->vertex_i == i)
                            {   
                                if(p->mark == 0)
                                {
                                    dist[p->vertex_i][p->vertex_j] = p->value;
                                    path[p->vertex_i][p->vertex_j] = p->vertex_i;
                                    dist[p->vertex_j][p->vertex_i] = p->value;
                                    path[p->vertex_j][p->vertex_i] = p->vertex_j;
                                    p->mark = 1;
                                }
                                p = p->i_link;
                            }
                            else
                            {
                                if(p->mark == 0)
                                {
                                    dist[p->vertex_i][p->vertex_j] = p->value;
                                    path[p->vertex_i][p->vertex_j] = p->vertex_i;
                                    dist[p->vertex_j][p->vertex_i] = p->value;
                                    path[p->vertex_j][p->vertex_i] = p->vertex_j;
                                    p->mark = 1;
    
                                }
                                 p = p->j_link;
                            }
    
    
                    }
                }
    
                    for(i = 0;i <= this->n;i++)
                        {
                            for(j = 0;j <= this->n;j++)
                            {
                                cout<<dist[i][j] <<"--";
                            }
                            cout<<endl;
                        }
    
                int k;
                for(k = 0;k < this->n;k++)
                    for(i = 0;i < this->n;i++)
                        for(j = 0;j < this->n;j++)
                        {
                            if(dist[i][j] > (dist[i][k] + dist[k][j]))
                            {
                                dist[i][j] = dist[i][k] + dist[k][j];
                                dist[j][i] = dist[i][k] + dist[k][j];
                                path[i][j] = path[k][j];
                                path[j][i] = path[k][i];
                            }
                        }
    
    
    
            }
            void Display_minpath(int i,int j)
            {
                cout<<i<<"-->"<<j<<":"<<dist[i][j]<<endl;
    //因为path[i][j]记录的J的前一节点，所以输出会倒着来
                int p = i;
                while(p != j)
                {
                    cout << p << "--";
                    p = path[j][p];
    
                }
                cout << j <<endl;
            }