Lua 实现 Dijkstra 算法求解最短路径

以下是使用 Lua 语言实现的 Dijkstra 算法来求解从起点出发的最短路径的代码示例：\n\nlua\n-- 图数据结构\nlocal graph = {\n {0, 4, 0, 0, 0, 0, 0, 8, 0},\n {4, 0, 8, 0, 0, 0, 0, 11, 0},\n {0, 8, 0, 7, 0, 4, 0, 0, 2},\n {0, 0, 7, 0, 9, 14, 0, 0, 0},\n {0, 0, 0, 9, 0, 10, 0, 0, 0},\n {0, 0, 4, 14, 10, 0, 2, 0, 0},\n {0, 0, 0, 0, 0, 2, 0, 1, 6},\n {8, 11, 0, 0, 0, 0, 1, 0, 7},\n {0, 0, 2, 0, 0, 0, 6, 7, 0}\n}\n\n-- 获取图中的顶点数量\nlocal function getVertexCount(graph)\n return #graph\nend\n\n-- 找到距离数组中最小距离的顶点\nlocal function findMinDistance(distance, visited)\n local minDistance = math.huge\n local minIndex = -1\n for i = 1, #distance do\n if not visited[i] and distance[i] < minDistance then\n minDistance = distance[i]\n minIndex = i\n end\n end\n return minIndex\nend\n\n-- 打印最短路径\nlocal function printPath(parent, vertex)\n if parent[vertex] == -1 then\n io.write(vertex, " ")\n return\n end\n printPath(parent, parent[vertex])\n io.write(vertex, " ")\nend\n\n-- Dijkstra算法\nlocal function dijkstra(graph, start)\n local vertexCount = getVertexCount(graph)\n local distance = {}\n local visited = {}\n local parent = {}\n\n -- 初始化距离数组、访问数组和父节点数组\n for i = 1, vertexCount do\n distance[i] = math.huge\n visited[i] = false\n parent[i] = -1\n end\n\n -- 设置起点的距离为0\n distance[start] = 0\n\n -- 找到最短路径\n for _ = 1, vertexCount - 1 do\n local u = findMinDistance(distance, visited)\n visited[u] = true\n for v = 1, vertexCount do\n if not visited[v] and graph[u][v] ~= 0 and distance[u] + graph[u][v] < distance[v] then\n distance[v] = distance[u] + graph[u][v]\n parent[v] = u\n end\n end\n end\n\n -- 打印最短路径和距离\n for i = 1, vertexCount do\n if i ~= start then\n io.write("最短路径从 ", start, " 到 ", i, " 的路径为：")\n printPath(parent, i)\n io.write("，距离为 ", distance[i], "\n")\n end\n end\nend\n\n-- 测试\ndijkstra(graph, 1)\n\n\n这里的graph变量表示图的数据结构，其中的数字表示边的权重。dijkstra函数接受一个图和起点作为参数，并计算出从起点到所有其他顶点的最短路径。最后的测试代码会输出从起点到其他顶点的最短路径和距离。