1

我正在尝试从文本文件中实现距离矢量路由协议，并且遇到了障碍，因为我的算法没有找到节点之间的新连接。我的节点结构是

public class Node {

    int name;

    public int[][] connections, via;


    Node(int iName, int size) {
        name = iName;
        connections = new int[size][size];
        via = new int[size][size];
    }

}

我的搜索算法是

for(int i = 0; i < size; i++){
    for(int j = 0; j<size; j++){

        if(node.connections[i][j]!=MAX){

            for(int k = 0; k < size; k++){
                if((node.connections[i][j]+node.connections[j][k])<node.connections[i][k]&&(node.connections[i][j]+node.connections[j][k])>0){
                     node.connections[i][k] = node.connections[i][j] + node.connections[j][k];
                     node.via[i][k] = j;
                     node.via[k][i] = j;
                }
            }
        }
    }
}

如果我使用这些参数，我可以让它跟踪节点之间的连接，但仅限于那些最初定义了连接的节点。

4

1 回答 1

0

请参阅有关 Floyd-Warshall 算法的链接。顺序应该像网站上的这个伪代码：

for k from 1 to |V|
    for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][k] + dist[k][j] < dist[i][j] then
         dist[i][j] ← dist[i][k] + dist[k][j]

编辑： 基于上面的伪代码，代码应该是这样的：

for(int k = 0; k < size; i++){
    for(int i = 0; j<size; j++){
        for(int j = 0; j < size; j++){
            if((node.connections[i][k]+node.connections[k][j])<node.connections[i][j]
                &&(node.connections[i][k]+node.connections[k][j])>0){
                node.connections[i][j] = node.connections[i][k] + node.connections[k][j];
                node.via[i][j] = k;
            }
        }
    }
}

循环的顺序很重要，因为循环体的行为会有所不同。第一步是选择路径的大小（k + 1 是我们正在优化的路径的大小，从大小为 1 的路径开始）。第二步是选择一个起始节点。第三步是选择一个端节点。然后，该算法找到从起始节点到另一个节点的大小为 1 的最短路径。第二个循环遍历所有起始节点以找到所有大小为 1 的最佳路径。然后，增加大小以找到所有大小为 2 的最佳路径，从大小为 1 的最佳路径构建。这一直持续到甚至考虑使用图中所有节点的路径。

于 2013-05-06T01:08:16.430 回答