更新感谢一些社区成员的评论，我意识到有一些类似的问题，但它们可能有点不同，请允许我进一步解释。实际上，我希望在实际问题中使用相同的方法，所以简单地说：
完全允许在不同路径中重复使用边
从a到b的唯一（或新）路径定义为具有任何不同顶点的顶点集合。
让我使用一个来自python数据结构和算法分析的测验，由bradley.n miller和david l。让我来解释我的问题。
答：考虑把单词傻瓜转化为圣人的任务，也称为单词梯形问题。在解决单词阶梯问题时，一次只能替换一个字母，并且每个步骤的结果必须是一个单词，而不是不存在的单词。
输入：

FOUL
FOOL
FOIL
FAIL
COOL
FALL
POOL
PALL
POLL
POLE
PALE
PAGE
SALE
POPE
POPE
SAGE

我们可以很容易地找到从傻瓜到圣人的道路，正如布拉德利所示：在这里输入图像描述
我使用广度优先搜索（bfs）来解决问题：

class Vertex: 
def __init__(self, key, value = None):
    self.id = key
    self.connectedTo = {}
    self.color = 'white'
    self.dist = sys.maxsize
    self.pred = []
    self.disc = 0
    self.fin = 0
    self.value = value, 
    #self.GraphBulided = False
    self.traverseIndex = 0
    self.predNum = 0

def addNeighbor(self, nbr, weight=0): 
    self.connectedTo[nbr] = weight

def __str__(self): 
    return '{} connectedTo: {}'.format(self.id, \
    str([x.id for x in self.connectedTo]))

def setColor(self, color):
    self.color = color

def setDistance(self, d): 
    self.dist = d

# I want store all  Pred for next traverse so I use a list to do it

def setPred(self, p, list = False): 
    if not list: 
        self.pred = p
    else: 
        self.pred.append(p)
        self.predNum += 1

def setDiscovery(self,dtime):
    self.disc = dtime

def setFinish(self,ftime):
    self.fin = ftime

# def setGraphBulided(self, tag = True):

# self.GraphBulided = tag

def getFinish(self):
    return self.fin

def getDiscovery(self):
    return self.disc

def getPred(self):
    if isinstance(self.pred, list):
        if self.traverseIndex < self.predNum:
            return self.pred[self.traverseIndex]
        else: 
            return self.pred[-1]
    else: 
        return self.pred

def __hash__(self):
    return hash(self.id)

def getPredById(self): 
    if self.traverseIndex < self.predNum and isinstance(self.pred, list): 
        pred = self.pred[self.traverseIndex]
        self.traverseIndex += 1
        print("vertix {}: {} of {} preds".format(self.id, self.traverseIndex, self.predNum))
        return [pred, self.traverseIndex]
    else: 
        pred =  None
        return [pred, None]

def getCurrPredStaus(self): 
    #if not self.pred: 
    #    return None
    return self.predNum - self.traverseIndex

def getDistance(self):
    return self.dist

def getColor(self):
    return self.color   

def getConnections(self): 
    return self.connectedTo.keys()

def getId(self): 
    return self.id

def getWeight(self, nbr): 
    return self.connectedTo[nbr]

def getValue(self): 
    return self.value

def findPath(self, dest): 
    pass

class Graph: 
def __init__(self):  
    self.vertList = {}
    self.numVertics = 0
    self.verticsInSerach = set()
    self.GraphBulided = False

def addVertex(self, key, value = None): 
    self.numVertics = self.numVertics + 1
    newVertex = Vertex(key, value=value)
    self.vertList[key] = newVertex
    return newVertex

def getVertex(self, n): 
    if n in self.vertList: 
        return self.vertList[n]
    else: 
        return None

def __contains__(self, n): 
    return n in self.vertList

def addEdge(self, f, t, cost = 0, fvalue = None, tvalue = None): 
    if f not in self.vertList:
        nv = self.addVertex(f, fvalue)
    if t not in self.vertList: 
        nv = self.addVertex(t, tvalue)
    self.vertList[f].addNeighbor(self.vertList[t], cost)

def setGraphBulided(self, tag = True): 
    self.GraphBulided = tag

def getVertices(self): 
    return self.vertList.keys()

def setGraphBulided(self, tag = True): 
    self.GraphBulided = tag

def setSerachedVertixs(self, vertix): 
    self.verticsInSerach.add(vertix)

def getGraphBulided(self): 
    return self.GraphBulided

def getSerachedVertixs(self): 
    return self.verticsInSerach

def __iter__(self): 
    return iter(self.vertList.values())

def __hash__(self):
    hashIds = [x for x in self.getVertices()]
    if len(hashIds) > 0 and hashIds[0]: 
        return hash(', '.join(hashIds))
    else: 
        return None

下面是一些用于构建图形的附加函数

def buildGraph(wordFile, DFSgraph = False): 
d = {}
g = Graph()
if DFSgraph: 
    g = DFSGraph()
wfile = open(wordFile)
for line in wfile: 
    word = line[:-1]
    for i in range(len(word)):
        bucket = word[:i] + '_' + word[i+1:]
        if bucket in d: 
            d[bucket].append(word)
        else:
            d[bucket] = [word]
for bucket in d.keys(): 
    for word1 in d[bucket]:
        for word2 in d[bucket]: 
            if word1 != word2: 
                g.addEdge(word1, word2) 
wfile.close()   
return g

class Queue:
def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def enqueue(self, item):
    self.items.insert(0,item)

def dequeue(self):
    return self.items.pop()

def size(self):
    return len(self.items)

def bfs(g, start, listpred = False): 
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0): 
    currentVert = vertQueue.dequeue()
    if currentVert.getConnections(): 
        g.setSerachedVertixs(currentVert)
    for nbr in currentVert.getConnections(): 
        #print('sreach {}'.format(currentVert.getId()))
        if (nbr.getColor() == 'white' or nbr.getColor() == 'gray'):
            nbr.setColor('gray')
            nbr.setDistance(currentVert.getDistance() + 1)
            if nbr.predNum > 0 and currentVert.getId() not in [x.getId() for x in nbr.pred]: 
                nbr.setPred(currentVert, listpred)
            elif nbr.predNum == 0: 
                nbr.setPred(currentVert, listpred)
            vertQueue.enqueue(nbr)
    currentVert.setColor('black')

因此，我们可以很容易地找到所需的最短路径（如果我们只为一个vertix存储一个pred）。

wordGraph = buildGraph('fourletterwords1.txt', DFSgraph=False)    
    bfs(wordGraph, wordGraph.getVertex('FOOL'), listpred=True) 
    def traverse(y): 
        x=y 
        while(x.getPred()):
            print(x.getPred())
            x = x.getPred()
        print(x.getId())    
    traverse(wordGraph.getVertex('SAGE'))

但是，我仍然不知道如何正确地追踪所有路径，你能给我一些建议吗？