Shortest path for gigantic maze (HUGE)

Question

I need to solve a shortest path algorithm problem (in C).

Basically I am given a file that contains the total number of rows and columns of a (sparse) matrix, the number of non zero entries (called doors) and finally the position and value of those entries (row, column, value). In this maze I have to find out the cheapest path from entry (0,0) to any other point(position also read from the file). Every time I cross one door the cost increases and the cells that are 0 cost nothing.

There are some rules like you cannot pass trough two or more doors in a row and certain doors whose value is -1 cannot be crossed. in the end I have to print the position of the doors I passed trough (the ones given in the file). It doesn't matter how many empty cells I crossed.

Anyway, the problem here is that the matrix can be 10⁵ x 10⁵ or more... I stored the non zero entries in what is called a sparse matrix I guess, and it works:

typedef struct node {
    struct node *down; 
    struct node *right; 

    long int PL, PC, PV;
} node;

typedef struct _Mat {
    long int NL, NC, P, x, y; //Number of lines,columns,non zero cells, and position of destination
    node **rowList; 
    node **colList;         
} Mat

The thing is I'm having trouble figuring out what to do next. With just this structure I don't think I can solve the maze.

Should I create a graph of the matrix (including the zeros) so after that I can apply an algorithm like Dijkstra's? I think this must be solved trough a graph, but the graph would be huge... Another idea is to group up a big group of non zero cells that are bounded by some doors and consider them to be only one node. This way the graph is smaller but I have no idea how to do this.

If that's the best solution, how can I implement it? Or am I completely wrong? Is my data structure useless?

Answer 1

Maybe A* can help you:

Link

This algorithm can find the optimal path in a graph, which you can convert your maze to.