请教一条图里面找最短路径的问题
帮忙想下，一个带权无向图，给定终点和起点，以及终点和起点中的m个点，如何找出经过终点起点以及这m个点的最短路径。(除了遍历它们的顺序外，还有好的办法么,点可以重复走，只要距离最短就行了)
[解决办法]
that 's travelling salesman problem=.=
An NP complete problem...I dont think it is solvable in general.
[解决办法]
Dijkastra算法又不是遍历，只要找到需要求最短路的点就退出了，但是它不支持带负权环的图。
int matrix[20][20]={0},n;//邻接矩阵,n表示节点数
bool link[20][20]={0};//link[i][j]==true表示从i到j有无向边
int digkastra(int st,int ed)
{
int i,j,dist[20];//dist记录从st到各点的最短路
int sel,min;
bool mark[20]={0};
mark[st]=true;
for(i=0;i<n;i++)
if(link[st][i])
dist[i]=matrix[st][i];
else
dist[i]=9999;
for(i=1;i<n;i++)
{
min=9999;
for(j=0;j<n;j++)
if(!mark[j]&&min>dist[j])
{
sel=j;min=dist[j];
}
if(min==9999)return dist[ed];//找不到相连的边
mark[sel]=true;
if(mark[ed])return dist[ed];//计算了st-ed的最短路
for(j=0;j<n;j++)
if(!mark[j]&&link[sel][j]&&dist[j]<dist[sel]+matrix[sel][j])
dist[i]=dist[sel]+matrix[sel][i];
}
return dist[ed];
}
[解决办法]
用递归应该可以！
[解决办法]
先算出m个点的两两最短距离，转化成新图就会发现，这个问题就是个路行商问题，是NP-complete
要求最优解，除了遍历他们的顺序也没什么太好的办法
如果求较优解，你可以考虑一些近似算法
