给定六个城市之间的距离，求从某一个城市起，每个城市恰好经过一次最后返回，求最短路径matlab

这是一个典型的旅行商问题（TSP），可以使用动态规划或回溯算法来解决。这里给出一个使用动态规划的方法来求解最短路径。

假设有6个城市，分别为A、B、C、D、E、F，它们之间的距离可以用一个6x6的矩阵来表示：

    A   B   C   D   E   F
A   0   2   3   4   5   6
B   2   0   4   5   6   7
C   3   4   0   6   7   8
D   4   5   6   0   8   9
E   5   6   7   8   0   10
F   6   7   8   9   10  0

其中矩阵的主对角线上的元素都是0，表示从一个城市到自己的距离为0。

设dp[i][S]表示从起点出发，经过集合S中的城市，最后到达城市i的最短距离。

则有状态转移方程：

dp[i][S] = min{dp[j][S-{i}] + dist[j][i]}，其中j∈S，j≠i

其中，dist[j][i]表示从城市j到城市i的距离，即上面矩阵中的元素。

最终的答案为：

min{dp[i][{1,2,3,4,5}]+dist[i][0]}，其中i∈{1,2,3,4,5}

即从任意一个城市出发，经过所有城市，最后回到起点的最短距离。

下面给出MATLAB代码实现：

% 城市距离矩阵
dist = [0 2 3 4 5 6;
        2 0 4 5 6 7;
        3 4 0 6 7 8;
        4 5 6 0 8 9;
        5 6 7 8 0 10;
        6 7 8 9 10 0];

n = size(dist, 1);  % 城市数量
S = 1:n;  % 城市集合

% 动态规划求解
dp = inf(n, 2^n);  % 初始化为无穷大
dp(1, 1) = 0;  % 起点到自己的距离为0
for j = 2:n
    for k = 1:2^n-1  % 枚举所有子集
        if bitand(k, bitshift(1, j-1)) == 0  % S集合中包含城市j
            continue
        end
        Sj = bitset(k, j-1, 0);  % S集合去掉城市j
        for i = 1:n
            if bitand(Sj, bitshift(1, i-1)) == 0  % Sj集合中包含城市i
                continue
            end
            dp(j, k) = min(dp(j, k), dp(i, Sj) + dist(i, j));
        end
    end
end

% 输出结果
ans = inf;
for i = 2:n
    ans = min(ans, dp(i, bitshift(1, n)-1) + dist(i, 1));
end
disp(ans);