请问python字符创中如何计算收尾相接的最短最长路径

Question

请问python字符创中如何计算收尾相接的最短最长路径

1.主要是要收尾相接
2.每接上去一个，权重为1
题目一：找出字符串中最长、最短路径
题目二：根据设置权重值，找出该权重下的最长最短路径，比如说2，就是1-2范围内
刚入python的坑，求大神指导

例子：
字符串：A/B,B/C,B/D,C/A,D/B

最长路径：
C->A->B->D 权重3

中间路径
A->B->C 权重2
A->B->D 权重2
B->C->A 权重2
D->B->C 权重2
C->A->B 权重2

最短路径：
B->D 权重1
D->B 权重1

Answer 1

你这个问题是关于图（graph）的算法。Python里有很多关于graph的实现库。据我所知networkX应该能完成你的这个任务。具体的步骤是：
1.根据你的输入构造一个有向图
2.从该有向图中生成最小生成树 （Minimum Spanning Tree）
3.所有没有包含在最小生成树的边被称为回边，事实上每条回边意味着一条闭合回路
4.在最小生成树上每个节点都有一个层级，根节点为0，其它节点的层级为其父节点的层级加1
5.每条闭合回路的长度就是标识该回路的回边的两个节点的层级之差再加上1