如何在C ++中计算有向图直径 [英] How to compute directed graph diameter in C++

问题描述

我有一个矩阵给出的有向图，我需要编写一个计算它的直径的程序（C ++）。我真的迷失了，当谈到这个。有没有一个已知的算法？ \

I have a directed graph given by a matrix and I need to write a program (C++) that computes it's diameter. I'm really lost when it comes to this. Is there a known algorithm for this? \

我认为它应该如何：

• 转换为无向图（对于任何有向矩阵[i] [j]！= 0，其中i从1到nrNodes并且j从i + 1到nrNodes，make matrix [j] [i] = matrix [i] [j] = directedMatrix [i]计算任何2个节点的最大距离（distaceMatrix [i] [j] =从节点i到节点j的最大距离; distanceMatrix [i] [i] = MIN）


• 从上述矩阵中找出最大值，这是我们的答案。

思考和优化？

推荐答案

假设节点数不是太大，一个简单的解决方案是使用Floyd-Warshall算法在所有节点对之间的最短路径，然后简单地采取最大的一个。以下代码演示了它：

Assuming that the number of nodes is not too great, a simple solution would be to use Floyd-Warshall algorithm to find the shortest paths between all pairs of nodes and then simply to take the greatest one. The following code demonstrates it:

#include <cstdio>

using namespace std;

#define MAX 107
#define NOT_CONNECTED -1

int distance[MAX][MAX];

//number of nodes
int nodesCount;

//initialize all distances to 
void Initialize(){
    for (int i=0;i<MAX;++i){
        for (int j=0;j<MAX;++j){
            distance[i][j]=NOT_CONNECTED;
        }
        distance[i][i]=0;
    }
}

int main(){

    Initialize();

    //get the nodes count
    scanf("%d", &nodesCount);

    //edges count
    int m;
    scanf("%d", &m);

    while(m--){
        //nodes - let the indexation begin from 1
        int a, b;

        //edge weight
        int c;

        scanf("%d %d %d", &a, &b, &c);
        distance[a][b]=c;
    }

    //Floyd-Warshall
    for (int k=1;k<=nodesCount;++k){
        for (int i=1;i<=nodesCount;++i){
            if (distance[i][k]!=NOT_CONNECTED){
                for (int j=1;j<=nodesCount;++j){
                    if (distance[k][j]!=NOT_CONNECTED && (distance[i][j]==NOT_CONNECTED || distance[i][k]+distance[k][j]<distance[i][j])){
                        distance[i][j]=distance[i][k]+distance[k][j];
                    }
                }
            }
        }
    }

    int diameter=-1;

    //look for the most distant pair
    for (int i=1;i<=nodesCount;++i){
        for (int j=1;j<=nodesCount;++j){
            if (diameter<distance[i][j]){
                diameter=distance[i][j];
                printf("%d %d\n", i, j);
            }
        }
    }

    printf("%d\n", diameter);

    return 0;
}

这篇关于如何在C ++中计算有向图直径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！