Pass matrix as function parameter?

Question

I’m studying Dijkstra’s algorithm and I haven’t tried using adjacency lists yet. I knew I could solve the problem with a matrix, but the fact is that I can not receive the matrix in the function.
If I put the code right into main works as expected.
This is the prototype I tried to use:

/*
 * v = grafo em forma de matriz
 * n = qtd de vértices
 * o = origem
 */
int * Dijkstra ( int v[][], int n, int o );

Answer 1

In C, you need to specify the size of all dimensions of a matrix that is function argument, except the size of the leftmost dimension. For example, if you set that your matrices will always be 100x100, you can set the type of your function like this:

int * Dijkstra ( int v[100][100], int n, int o );

or so:

int * Dijkstra ( int v[][100], int n, int o );

The reason for this comes from the way in which C matrices are represented in memory. Lines are placed sequentially on a vector. For example, the 3x3 matrix

10 20 30
40 50 60
70 80 90

It is represented in memory as a size 9 vector

M[i][j] ->    10 20 30 40 50 60 70 80 90
i       ->     0  0  0  1  1  1  2  2  2
j       ->     1  2  3  1  2  3  1  2  3

When you access the field (i,j) of the 3x3 matrix, what C does under the cloths is to access the field 3*i + j of the "vector zão". Therefore, the compiler has to know at compile time how many columns there are in each row, which is the factor that multiplies the i.

If you don’t want to define the dimensions of your matrix at compile time there are some alternatives you can do. The most common is to use a vector of vectors instead of a multidimensional vector. Thus, its matrix has a type "pointer vector for integer" int ** instead of the "two-dimensional vector of integers 100x100" int [100][100].

 M ->  |*| --> [10 20 30]
       |*| --> [40 50 60]
       |*| --> [70 80 90]

An example of how to allocate an Mxn matrix:

// Alocando a matriz dinâmicamente
int ** mat = malloc((sizeof int*) * M;
int  * buf = malloc((sizeof int) * M * N);
for(int i=0; i<M; i++){
    mat[i] = &buf[N*i];
}

// Usando a matriz:
for(int i=0; i<M; i++){
    for(int j=0; j<N; j++){
        mat[i][j] = f(i,j);
    }
 }

 // Libere a memória alocada dinamicamente quando você acabar de usar.
 free(mat);
 free(buf);