问题描述不展开了，感兴趣可以自己搜一下。csdn上这篇文章介绍的很详细，可以看一下 ，http://blog.csdn.net/q345852047/article/details/6626684 感谢作者辛勤码字，我就偷懒啦～

1.贪心

"""
    Functions:
        find_path:
    Data structures:
        path_vertexs：保存遍历过的顶点，防止重复遍历
        path_length：保存遍历过的每条边的权值
"""
def find_path(j):
    path_vertexs.append(j)  #把该节点标记为已走过    
    row=c[j]  
    #创建copy_row,删除row中已走过的顶点,防止直接在row上操作.
    copy_row=[value for value in row]
    walked_vertex=[]
    for i in path_vertexs:#已走过的顶点
        walked_vertex.append(copy_row[i])
    for vertex in walked_vertex:
        copy_row.remove(vertex)
    #寻找row中的未遍历过的最短边
    if len(path_vertexs)<5:
        min_e=min(copy_row)
        j=row.index(min_e)
        path_length.append(min_e)
        find_path(j)
    else:
        min_e=c[j][0]
        path_length.append(min_e)
        path_vertexs.append(0)
    return path_vertexs,path_length

def print_path(vertexs,lengths):
    path=''    
    vertexs=[vertex+1 for vertex in vertexs]
    for i,vertex in enumerate(vertexs):
        path+=str(vertex)
        if i==5:
            break
        path+='->'
    print("最小总旅费为：",sum(lengths))
    print("路 径：",path)

if __name__ == "__main__":
    c=[[0,3,1,5,8],
    [3,0,6,7,9],
    [1,6,0,4,2],
    [5,7,4,0,3],
    [8,9,2,3,0]]
    path_length=[]
    path_vertexs=[]   
    path_vertexs,path_length=find_path(0)
    print_path(path_vertexs,path_length)
    
"""    从顶点0开始：
        把0加入到已遍历集合，寻找第0行的最小值，并返回其所在列j，
    转到第j行，寻找未遍历过的最短边。
        把顶点加入已遍历集合，保存对应的最小权值。 
    停止： 当走过的顶点集长度=5时，停止
"""```


二. 动态规划

Note： 当前代码只输出最短路径长度，没有输出最短路径，以后有时间补上，实在要是忘了....那就忘了吧～

以下代码采用动态规划的思想，实现TSP最短路径的求解问题。

matrix for undirected graph

c=[[0,3,1,5,8],
[3,0,6,7,9],
[1,6,0,4,2],
[5,7,4,0,3],
[8,9,2,3,0]]
n=len(c)

初始化d

d=[[0 for j in range(2**(n-1))] for i in range(n)]
for i in range(1,n): # 1234
d[i][0]=c[i][0]

用二进制表示顶点集合v，j代表其相应的编号：

"""0 000 {}
1 001 {1}
2 002 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}
"""

判断集合是否包含某元素 judge()

def judge(i,j):#3=1+2 5=101 1+3 6=3+2
involve=(i&j)==0#结果为0说明不包含
return involve #若j不包含i 返回true

计算j包含那些顶点,利用与运算

def find_vertex(j):
vertexs=[]#j包含哪几个顶点
for v in range(n-1):
if (2v)&j!=0:#0123 2i表示顶点i+1
vertexs.append(v+1) #说明j包含顶点v+1
return vertexs

-------------------

for j in range(2(n-1)):# j从0-15
for i in range(1,n):# 1234
temp=[]
vertexes=find_vertex(j)
if i not in vertexes:
for k in vertexes:
temp.append(c[i][k]+d[k][j-2(k-1)])
if temp:
d[i][j]=min(temp)
print(d[i][j])

对v[2(n-1)-1]中的每个元素k计算，d[0][2(n-1)-1]=min(c[0][k]+d[k][...])

temp=[]
for k in find_vertex(2(n-1)-1):
j=2(n-1)-1
new_j=2(n-1)-1-2(k-1)
temp.append(c[0][k]+d[k][new_j])
d[0][2**(n-1)-1]=min(temp)

print("Shortest path length:",d[0][2**(n-1)-1])
for row in d:
for col in row:
print(str(col)+" ",end="")
print()