A graph G consists of a set of vertices v0 vn1 and a set

A graph G consists of a set of vertices {v0, · · · , vn1} and a set of edges {e1, · · · , em1}. An edge connects two vertices vi and vj . In a weighted graph, each edge also has a weight, which is usually a positive number.

1. Given a weighted graph in which every pair of vertices is connected by an edge, write a brute-force Python program (using the backtracking framework) to find a tour of all vertices with minimal total weight. A tour is a path that begins with one vertex and ends at the same vertex.

Solution

def Funct(graph, start, end, q = []):
answerwer=[]
initPath = [start]
q.append(initPath)
while len(q) != 0:
tmpPath = q.pop(0)
lastNode = tmpPath[-1]
print \'path:\', printPath(tmpPath)
if lastNode == end:
answerwer.append(tmpPath)
qt=[]
for linkNode in graph.childrenOf(lastNode):
if linkNode not in tmpPath:
newPath = tmpPath + [linkNode]
qt.append(newPath)
q[:0]=qt
return answerwer
def testSP():
mitMap = load_map(\"mit_map2.txt\")
sp = Funct(mitMap, mitMap.nodes[0], mitMap.nodes[5])
print \'Shortest path is\', printPath(sp)