c - 巨型迷宫的最短路径(HUGE)

Question

我需要解决最短路径算法问题(用 C 语言)。

基本上，我得到一个文件，其中包含(稀疏)矩阵的总行数和列数、非零条目(称为门)的数量以及最后这些条目的位置和值(行、列、值) )。在这个迷宫中，我必须找出从条目 (0,0) 到任何其他点的最便宜路径(位置也从文件中读取)。每次我穿过一扇门，成本就会增加，而 0 的单元格则不需要任何成本。

有一些规则，比如你不能连续穿过两扇或更多门，以及某些值为 -1 的门不能穿过。最后我必须打印我经过的门的位置(文件中给出的门)。我穿过多少个空单元格并不重要。

无论如何，这里的问题是矩阵可以是 10⁵ x 10⁵ 或更多...我猜我将非零条目存储在所谓的稀疏矩阵中，并且它有效:

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

问题是我不知道下一步该做什么。仅凭这种结构，我认为我无法解决迷宫问题。

我应该创建一个矩阵图(包括零)，以便之后我可以应用像 Dijkstra 那样的算法吗？我认为这必须通过图表来解决，但图表会很大......另一个想法是将一大群由一些门包围的非零单元格分组，并将它们视为只有一个节点。这样图表会更小，但我不知道该怎么做。

如果这是最好的解决方案，我该如何实现？或者我完全错了？我的数据结构没用吗？

Answer 1

也许 A* 可以帮助您:

Link

该算法可以在图中找到最佳路径，您可以将迷宫转换为该路径。