我正在查看此pdf，因为我正在尝试构建 MSSP（多源最短路径），但我缺乏如何构建交叉树的知识。直到现在我创建了生成树，因此创建了平面图，但我卡住了，因为我不知道如何构建它的对偶。是否有任何特定的算法/方法或任何论文可以帮助我解决这个问题？当我搜索时，找不到任何有用的东西。
问问题
903 次
1 回答
1
如果您还没有，则需要组合嵌入。有一些有效的算法可以从关联结构中获得一个，但是平面图的自然来源通常具有自然嵌入。有很多方法可以表示嵌入。我使用排列 π 以逆时针顺序将每个半边映射到下一个半边，并具有相同的头顶点。每个（非隔离）顶点与传入半边的循环链接列表相关联。
令 rev 为将每个半边映射到另一半的排列，具有相反的头和尾顶点。对偶图的嵌入排列是 π 和 rev 的组合。它按顺时针顺序将每个半边映射到面上的下一个半边（或在无限面上逆时针，因为您正在查看它的背面）。如果您手动尝试一些示例，这会更清楚。
从初始根计算最短路径后（我使用了 Dijkstra，除非您的 MSSP 实现比我的快得多，否则使用渐近更快的算法并没有太大的相对改进），进行深度优先搜索，其中属于最短路径树的边被忽略。（另一种选择是以 Euler-tour 顺序访问叉指树的半边，但这种方法似乎会导致额外的对数时间动态树操作。）
于 2013-03-07T14:45:09.997 回答