getSearchTree

方法描述

getSearchTree 方法是 Dijkstra 算法的一部分，它将基于节点和边参数，返回一个搜索树（search tree）用于查找最短路径，以及每个节点的前驱节点和距离。

方法参数

• graph（必需）：一个二维矩阵，用于表示图形的边权重。矩阵的行数和列数应该等于节点数量。
• startNode（必需）：从该节点开始计算最短路径。这应该是一个整数值，表示节点的索引。
• endNode（可选）：计算到该节点的最短路径。这应该是一个整数值，表示节点的索引。
• customDistanceFunction（可选）：自定义距离函数，在计算距离时会使用该函数而非默认的计算距离函数，返回的距离必须为任意非负实数。

返回值

• 对象：一个包含搜索树的根节点、前驱节点和距离信息的对象。

方法示例

const graph = [
  [0, 2, 4, 0],
  [2, 0, 1, 4],
  [4, 1, 0, 3],
  [0, 4, 3, 0],
];

const result = yuka.dijkstra.getSearchTree(graph, 0, 3);

console.log(result);

输出：

{
  "root": 0,
  "predecessors": [null, 0, 1, 2],
  "distances": [0, 2, 3, 6]
}

注意事项

默认情况下，该方法使用默认距离函数：

function defaultDistanceFunction(a, b) {
  return a + b;
}

当 customDistanceFunction 被提供时，距离函数会被替换为自定义函数。该函数应该接受两个实数参数，返回它们之间的非负实数距离。对于衡量距离的应用程序，可以选择适当的加权公式和距离度量。

如果 endNode 参数未被提供，则搜索树包含从 startNode 到所有可达节点的最短路径。否则，搜索树会停止在 endNode，该节点也会被包括在搜索树内。

请注意，输入的图形必须是无向的，如果是有向的，则需要自行处理并将其转换为无向图形。默认情况下，任何具有 0 值的边都被视为未连接的节点。因此，如果该图形具有负权重边，则建议使用自定义距离函数以避免错误结果。