用一个贪婪算法可以解决这个问题，假设从A到Z的最短路径为A->C->G->Z，那么这条路径也是A到G、A到C的最短路径，因为如果A到G还有更短的路径，那么A到Z的距离就还可以更短了，即这条路径不是最短的。因此我们从A开始延伸，一步步地确定A到其它地点的最短路径，直到扩散到Z。

在无权的情况下，如上面任意相邻城镇的距离相等，和A直接相连的节点必定是A到这个节点的最短路径，如上图A到B、C、F的最短路径为A->B、A->C、A->F，这三个点的最短路径可标记为已知。和C直接相邻的是G和D，C是最短的，所以A->C-G和A->C->D也是最短的，再往下一层，和G、D直接相连的分别是E和Z，所以A->C->G->Z和A->C->D->E是到Z和E的一条最短路径，到此就找到了A->Z的最短路线。E也可以到Z，但是由于Z已经被标为已知最短了，所以通过E的这条路径就被放弃了。

和A直接相连的做为第一层，而和第一层直接相连的做为第二层，由第一层到第二层一直延伸目标结点，先被找到的节点就会被标记为已知。这是一个广度优先搜索。

而在有权的情况下，刚开始的时候A被标记为已知，由于A和C是最短的，所以C也被标记为已知，B和F不会标记，但是它们和A的距离会受到更新，由初始化的无穷大更新为A->B和A->F的距离。在已查找到但未标记的两个点里面，A->F的距离是最短的，所以F被标记为已知，这是因为如果存在另外一条更短的未知的路到F，它必定得先经过已经查找到的点（因为已经查找过的点是A的必经之路），这里面已经是最短的了，所以不可能还有更短的了。F被标记为已知之后和F直接相连的E的距离得到更新，同样地，在已查找到但未标记的点里面B的距离最短，所以B被标记为已知，然后再更新和B相连的点的距离。重复这个过程，直到Z被标记为已知。

标记起始点为已知，更新表的距离，再标记表里最短的距离为已知，再更新表的距离，重复直到目的点被标记，这个算法也叫Dijkstra算法。

现在来实现一个无权的最短路径，如下代码所示：

calPath(){ var pathTable = new Array(this.cells); for(var i = 0; i < pathTable.length; i++){ pathTable[i] = {known: false, prevCell: -1}; } pathTable[0].known = true; var map = this.linkedMap; //用一个队列存储当前层的节点，先进队列的结点优先处理 var unSearchCells = [0]; var j = 0; while(!pathTable[pathTable.length - 1].known){ while(unSearchCells.length){ var cell = unSearchCells.pop(); for(var i = 0; i < map[cell].length; i++){ if(pathTable[map[cell][i]].known) continue; pathTable[map[cell][i]].known = true; pathTable[map[cell][i]].prevCell = cell; unSearchCells.unshift(map[cell][i]); if(pathTable[pathTable.length - 1].known) break; } } } var cell = this.cells - 1; var path = [cell]; while(cell !== 0){ var cell = pathTable[cell].prevCell; path.push(cell); } return path; }

这个算法实现的关键在于用一个队列存储未处理的结点，每处理一个结点时，就把和这个结点相连的点入队，这样新入队的结点就会排到当前层的结点的后面，当把第一层的结点处理完了，就会把第二层的结点都push到队尾，同理当把第二层的结点都出队了，就会把第三层的结点推到队尾。这样就实现了一个广度优先搜索。

在处理每个结点需要需要先判断一下当前结点是否已被标记为known，如果是的话就不用处理了。

在pathTable表格里面用一个prevCell记录到这个结点的上一个结点是哪个，为了能够从目的结点一直往前找到到达第一个结点的路径。最后找到这个path返回。

只要有这个path，就能够计算位置画出路径的图，如下图所示：

这个算法的速度还是很快的，如下图所示：

当把迷宫的规模提高到200 * 200时：

生成迷宫的时间就很耗时了，花费了10秒：

于是想着用WASM提高生成迷宫的效率，看看能提升多少。我在《WebAssembly与程序编译》这篇里已经介绍了WASM的一些基础知识，本篇我将用它来生成迷宫。

4. 用WASM生成迷宫

我在《WebAssembly与程序编译》提过用JS写很难编译，所以本篇也直接用C来写。上面是用的class，但是WASM用C写没有class的类型，只支持基本的操作。但是可以用一个struct存放数据，函数名也相应地做修改，如下代码所示：

struct Data{ int *set; int columns; int rows; int cells; int **linkedMap; } data; void Set_union(int root1, int root2){ int *set = data.set; if(set[root1] < set[root2]){ set[root2] = root1; } else { if(set[root1] == set[root2]){ set[root2]--; } set[root1] = root2; } } int Set_findSet(int x){ if(data.set[x] < 0) return x; else return data.set[x] = Set_findSet(data.set[x]); }