寻求一种能够产生 N 条短路径的算法。
有人有在有向图中查找多条短路径的算法的经验吗？我的应用程序用于语言（查找同义词链），但从逻辑上讲，这可能用于地理或社交网络。我想要显着不同的路径，而不仅仅是沿途交换几个节点。我真的很想知道是否有办法避免“枢纽”，即大型机场或超级连接器；或者在语言中，有很多含义的单词。
（对于我的应用程序，我已经用 Dijkstra 和 A-star 解决了这个问题，但除了在获得第一条路径后更改权重之外，我还没有一个好的方法来获得多条路径。）
例如（如果是社交网络），我如何找到连接我和你的多条路径，沿途大多是不同的人。可能有 4-7 个分离点，这是可能的。对于语言和社交网络来说，通常有 6 度左右的分离度。即很少需要 20 个以上的节点。
我见过Dijkstra 算法来找到所有可能的最短路径，这是最短路径算法的一种变体，在寻找最短路径时，BFS 和 Dijkstra 算法有什么区别？，用 A* 算法找到几条最短路径——但没有一条是我所寻求的。
当然有人已经弄清楚了这一点，但我不知道要搜索什么。
几年来,我经常需要将(已排序)文本的行与匹配的第一个字段组合在一起,而我从未找到过优雅(即单行unix命令行)的方法.我想要的是与unix join命令的相似之处,但是join需要2个文件,每个键最多出现一次.我想从一个文件开始,其中一个键可能出现多个tile.
我有一个执行此操作的ruby和perl脚本,但是没有办法将我的算法缩短为单行.经过多年的UNIX的使用,我还在学习新的技巧有comm,paste,uniq,等,我怀疑有一个聪明的办法来做到这一点.
有一些相关的问题,比如将所有具有相同第一列的行连接到同一行 ; 命令行匹配第一个字段匹配的行(sed,awk等) ; 并将线条与匹配的键组合在一起 - 但这些解决方案从未真正提供干净可靠的解决方案.
这是示例输入:
apple:A fruit
apple:Type of: pie
banana:tropical fruit
cherry:small burgundy fruit
cherry:1 for me to eat
cherry:bright red
这是示例输出:
apple:A fruit;Type of: pie
banana:tropical fruit
cherry:small burgundy fruit;1 for me to eat;bright red
这是我理想的语法:
merge --inputDelimiter=":" --outputDelimiter=";" --matchfield=1 infile.txt
"matchfield"实际上是可选的.它可能永远是第一个领域.分隔符的后续出现应该被视为纯文本.
我不介意perl,ruby,awk单行,如果你能想到一个简短而优雅的算法.这应该能够处理数百万行输入.有任何想法吗？
希望分割内容行，保留标题。
我进行了大量的文本处理，并且我喜欢使用 unix one-liners，因为随着时间的推移，它们很容易组织（相对于大量的脚本），我可以轻松地将它们链接在一起，并且我喜欢（重新）学习如何使用经典的 UNIX 函数。我通常会使用短的 awk、perl 或 ruby 单行代码，具体取决于哪一种最优雅。
这里我有 X 行以逗号分隔的项目。我想把它们分开，保留标题。
输入：
animals = lizard, bird, bee, snake, whale, eagle, beetle, mule, hare, goose, horse, mouse, pig, dog, frog, bug, fish, duck, camel, squirrel, owl, chicken, pigeon, lion, sheep, bear, spider, deer, tiger, lobster, dinosaur, cat, goat, rat, cricket, rabbit, elephant, crow, fox, donkey, monkey, butterfly, crab, leopard, moth, shark, salmon, shrimp, mosquito, horseshoe crab
输出：
animals = lizard, bird, bee, snake, whale, eagle, beetle, mule, hare
animals …