搜索“服务器”和最短路径
我想不出解决这个问题的办法。我有组件(服务器)列表：
2-8
8-3
3-9
.因此，这意味着这些服务器是链接的，您可以从任何其他服务器开始访问所有服务器-所有服务器都通过其他服务器链接。问题是如何找出访问所有其他服务器的最短方式(步数)。每个环节都被认为是一个步骤。
示例：
1-2
2-7
2-8
2-9
2-3
3-4
4-5
4-6
答:3号服务器最多需要2步才能访问所有其他服务器。
解决此问题的最佳解决方案是什么？选择哪种数据结构来保存/读取文件中列出的数据，如示例所示？
P.S此任务将在C++中开发
回答 3
Stack Overflow用户
发布于 2010-12-15 11:44:31
你想要的是所谓的图形中心。您的算法文本可能会与所有成对的最短路径算法(Floyd-Warshall和Johnson算法)一起讨论。Here是一个简短的讨论
Stack Overflow用户
发布于 2010-12-15 12:15:51
您绝对希望将此数据表示为图形。具体地说，您需要一个distance matrix。
你可以用弗洛伊德-沃肖尔算法填充这个矩阵。
基本上，对于固定数量的服务器，N，do (在不完全的代码中)：
int dist[N][N];
fill(dist, N + 1);
for (i = [0,N)) dist[i][i] = 0;
foreach (edge e) dist[e.first][e.second] = dist[e.second][e.first] = 1
for (k = [0,N))
for (j = [0,N))
for (i = [0,N))
dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])然后dist[i][j]保存从服务器i到服务器j的距离。通过填充的距离矩阵，确定图的中心是很容易的。
Stack Overflow用户
发布于 2010-12-15 11:47:18
像这样的基本图形将由一个二维数组来表示。表示每个服务器的列，表示到其他服务器的距离的行您的示例为(初始化为-1以表示无法到达的状态，谢谢Chris)
1 2 3 4 5 6 7 8 9
1 0 1 -1 -1 -1 -1 -1 -1 -1
2 1 0 1 -1 -1 -1 1 1 1
3 -1 1 0 1 -1 -1 -1 -1 -1
4 -1 -1 1 0 1 1 -1 -1 -1
5 -1 -1 -1 1 -1 -1 -1 -1 -1
6 -1 -1 -1 1 -1 -1 -1 -1 -1
7 -1 1 -1 -1 -1 -1 -1 -1 -1
8 -1 1 -1 -1 -1 -1 -1 -1 -1
9 -1 1 -1 -1 -1 -1 -1 -1 -1然后填入两个数字，例如。对于第1列和第1行，在第2列有1的地方放入2(忽略1)，即3 7 8和9。第一列/行也是如此
1 2 3 4 5 6 7 8 9
1 0 1 2 -1 -1 -1 2 2 2
2 1 0 1 -1 -1 -1 1 1 1
3 2 1 0 1 -1 -1 -1 -1 -1
4 -1 -1 1 0 1 1 -1 -1 -1
5 -1 -1 -1 1 -1 -1 -1 -1 -1
6 -1 -1 -1 1 -1 -1 -1 -1 -1
7 2 1 -1 -1 -1 -1 -1 -1 -1
8 2 1 -1 -1 -1 -1 -1 -1 -1
9 2 1 -1 -1 -1 -1 -1 -1 -1对三个重复上述步骤。看一下距离为2 (3,7,8,9)的列。重复冲洗。
至于文件格式，行中的值对应该很好。
https://stackoverflow.com/questions/4446151
复制相似问题
腾讯云开发者
