如何在C ++中计算有向图直径 [英] How to compute directed graph diameter in C++
本文介绍了如何在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屋!
查看全文