小编Mar*_*nso的帖子

我正在尝试制作一个小型公共交通路线应用程序.

我的数据以下列结构表示:

graph = {'A': {'B':3, 'C':5},
     'B': {'C':2, 'D':2},
     'C': {'D':1},
     'D': {'C':3},
     'E': {'F':8},
     'F': {'C':2}}

哪里:

1. 图形dict键是一个节点
2. subdict键是2个节点之间的边
3. subdict value是边缘权重

我正在使用这里描述的find_shortest_path算法https://www.python.org/doc/essays/graphs/但由于递归而且它没有权重支持,所以它相当慢.

所以我转到Davide Epstein描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/(甚至更好的实现可以在评论中找到使用heapq)

它工作得很好,它真的很快,但我只获得最佳路线而不是所有可能路线的列表.这就是我陷入困境的地方.

有人可以帮助我,或者至少给出指示？我在图最短路径算法方面不是很好.

提前致谢!

我正在 Django 网站上工作，应该可以选择包含用户提供的成分的烹饪食谱。简而言之，该网站的理念是“你可以用冰箱里的食物制作东西”。

所以我做了2个模型

class Recipe (models.Model):
   name = models.CharField(max_length=255)
   ingredients = models.ManyToManyField(Ingredient)

class Ingredient (models.Model):
    name = models.CharField(max_length=255)

让我们想象一下，我有 as list ['egg','bread','meat','onion']。

现在我需要选择所有可以从成分列表中制作的食谱。问题是，某些食谱可能只有列表中的某些成分。
例如：

• 鸡蛋吐司=鸡蛋+面包
• 肉蛋吐司=肉+鸡蛋+面包
• 洋葱肉=肉+洋葱
• 等等...

所以我的问题是：是否可以从配料列表中选择所有可以制作的食谱，然后从配料列表中选择最接近的食谱+商店中的一些配料？

例如：recipes 有 4 个元素中的 3 个，因此我们将其添加到结果中。