2

我正在尝试使用邻接矩阵确定下一跳路由表。每个节点都知道该拓扑的完整邻接矩阵。我发现以前的帖子解释了如何做到这一点，但是，我不明白为什么我的错误。我有几个辅助函数，但它们的名称很直观，因此您可以跳到“开始路由计算”。

我使用邻接矩阵作为成本矩阵，它只有 0 和 1。由于某种原因，该算法似乎没有停止。队列卡在大小 1,3 或 5 上，具体取决于节点。

变量 rank 保存当前节点索引，它在 OpenMPI 中运行，因此每个进程（rank / node）独立运行这段代码。变量矩阵保存邻接矩阵。这是我正在使用的拓扑：

               0
             /    \
           1       2
       / /  | \   /  \
      3  4  5  6 7    8
        / \           |
       9  10          11

邻接矩阵：（如节点 3 所见，其中一个不会停止）；

1 1 1 0 0 0 0 0 0 0 0 0 
1 0 0 1 1 1 1 0 0 0 0 0 
1 0 0 0 0 0 0 1 1 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 1 1 0 
0 1 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 1 
0 0 0 0 1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 0

到目前为止我的代码：

int isFull(int *d, int size) {
    int i;

    for(i = 0; i < size; i++) {
        if(d[i] == INF) {
            return -1;
        }
    }
    return 1;
}
int vecSize(int *d, int size) {
    int counter = 0;
    int i;
    for(i = 0; i < size; i++) {
        if(d[i] != INF) {
            counter++;
        }
    }
    return counter;
}
bool List_contains(std::list<int > l, int val) {
    for (std::list<int>::const_iterator iterator = l.begin(), end = l.end(); iterator != end; ++iterator) {
        if (*iterator == val) {
            return true;
        }
    }
    return false;
}
int minimum (int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}
/* matrix is the complete adjacency matrix */


/* starting routing calculations
 *
 */
std::list <int > visited;
int *dist;
dist = (int*) calloc(size, sizeof(int));
visited.push_back(rank);

//debug
//printf("debug not empty %d\n", isFull(dist, size));
for(i = 0; i < size; i++) {
    if(matrix[rank][i] == 1) {
        dist[i] = 1;
    } else {
        dist[i] = INF;
    }
}
dist[rank] = 0;
int min;
while(isFull(dist,size) < 0) {
    if(rank == 3)
        printf("node - %d -debug -- list size %d\n",rank, vecSize(dist, size));
    //get the first node that isn't contained
    for(i = 0; i < size; i++) {
        if (!List_contains(visited, i) && min != rank) {
            min = i;
            break;
        }
    }

    for(i = 0; i < size; i++) {
        if((min >= dist[i]) && (!List_contains(visited, i)) && min != rank) {
            min = i;
        }
    }
    if(rank == 3)
        printf("min = %d\n", min);
    visited.push_back(min);

    for(i = 0; i < size; i++) {
        if((matrix[min][i] == 1) && (!List_contains(visited, i))) {
            dist[i] = minimum (dist[i], dist[min] + matrix[min][i]);
        }
    }
    if(rank == 3)
        //printf("rank %d dist = \n", rank);
    for(i = 0; i < size; i++) {
        if(rank == 3)
            printf("%d ", dist[i]);
    }
    if(rank == 3)
        printf("\n");
}
/*
 * finished routing calculations.
 */

这将是迄今为止的输出：http: //pastebin.com/x5wjKkyn

有人能指出我做错了什么吗？谢谢 ！稍后编辑：从技术上讲，该算法提供了正确的距离，它只是不会停止。（输出仅来自节点 0）

稍后编辑：似乎程序没有停止，因为对于某些节点，算法没有完成。

4

0 回答 0