c - 在邻接矩阵中随机添加 INFTY 值

Question

我想创建一个表示无向图的邻接矩阵(以实现 Dijkstra 算法)。我通过创建充满随机数的 N*N 矩阵来开始我的代码。但是，它希望使图形不完全连接，因此矩阵必须包含 INFTY，表示任何一对节点之间没有路径。因此，如何在矩阵生成过程中随机添加 INFNTY 值，如下所示:

#include <stdio.h> 
#include <string.h> 
#include <time.h>
#include <math.h>

#define INFTY 99  // Define Infinity as a macro

int main (int argc, char* argv[]) {
        /* Local Variables */
    int N = 40;             // Number of Nodes
    int SOURCE = 0;         // Selected Source
    int i,j;

    /* Matrix Allocation for edges */
    int *edge[N]; 
    for (i = 0; i < N; i++){
        edge[i] = malloc(N * sizeof(int));
    }

    /* Randomely fill the matrix with random integers from 0-10 */
    srand(0);
    for (i = 0; i < N; i++){
        for (j = 0; j < N; j++){
            if(i == j)
                edge[i][j] = 0;
            else
                edge[i][j] = rand() % 10; // Can I do something here to insert INFTY randomly. 
        }
    }
}

Answer 1

以下是您可以执行的操作:

for (i = 0; i < N; i++){
    for (j = 0; j < N; j++){
        if(i == j)
            edge[i][j] = 0;
        else {
            int r = rand() % 11
            edge[i][j] = r == 10 ? INFTY : r;
        }
}

这意味着大约每第 11 个边都是 INF。如果你想增加矩阵的稀疏性，你可以:

int sparsity_rate = 50; // measured in %
...
if (rand() % 1011 <= sparsity_rate)
    edge[i][j] = INFTY;
else
    edge[i][j] = rand() % 10;

sparsity_rate 告诉您图形的空闲程度(以 % 为单位)。在上面的示例中，大约 50% 的边将消失。