很莫名其妙的题目，如有知道的请指教。 是老师布置的作业
10 个解决方案
#1
upup
#2
是一维的点还是二位三维的点，是不是需要经过其他的点，可不可以重复经过某些点？你的问题说得不清不楚，请说明白一点
#3
这个程序我写了很久了,而且还是从我写的图类中截取出来的,可能有些地方不太对,不过算法的思想还可以看出来,你要的功能只要改一下就可以了.如果你想要我的可以运行的源程序的话,我可以EMAIL给你.不过它没有注释哟!另外,这个算法在数据结构的书中有源程序的,你可以找一本来看看.
int ShortPath(unsigned long NodeID1)
{
NType lPath[N][N];//建立路径表;N为结点数,NType为表中元素的类型
//初始化路径表
memset(lPath,-1, N^N*Sizeof(NType));
for (long i=0;i<N;i++)
{
lPath[0][i]=Graph[NodeID1][i];
if (lPath[0][i])
lPath[1][i]=i;
}
//搜索最短路径
for (long i=1;i<N;i++)
for (long j=0;j<N;j++)
{
long ttt=lPath[i][j];
if (ttt>=0)
for (long p=0;p<N;p++)
if (Graph[ttt][p]>0&&lPath[0][ttt]>0&&(lPath[0][p]==0||Graph[ttt][p]+lPath[0][ttt]<lPath[0][p]))
{
lPath[0][p]=Graph[ttt][p]+lPath[0][ttt];
for(long k=1;k<=i;k++)
lPath[k][p]=lPath[k][ttt];
lPath[i+1][p]=p;
}
}
//搜索的结果在lPath中,lPath[0][i]为结点NodeID1到结点i的最短路径长度,lPath[1][i]~lPath[a][i]为最短路径所经过的结点.
//一次可以找出NodeID1到其它所有结点的最短路径.
//Graph[N][N]为图的代权邻接矩阵
}
int ShortPath(unsigned long NodeID1)
{
NType lPath[N][N];//建立路径表;N为结点数,NType为表中元素的类型
//初始化路径表
memset(lPath,-1, N^N*Sizeof(NType));
for (long i=0;i<N;i++)
{
lPath[0][i]=Graph[NodeID1][i];
if (lPath[0][i])
lPath[1][i]=i;
}
//搜索最短路径
for (long i=1;i<N;i++)
for (long j=0;j<N;j++)
{
long ttt=lPath[i][j];
if (ttt>=0)
for (long p=0;p<N;p++)
if (Graph[ttt][p]>0&&lPath[0][ttt]>0&&(lPath[0][p]==0||Graph[ttt][p]+lPath[0][ttt]<lPath[0][p]))
{
lPath[0][p]=Graph[ttt][p]+lPath[0][ttt];
for(long k=1;k<=i;k++)
lPath[k][p]=lPath[k][ttt];
lPath[i+1][p]=p;
}
}
//搜索的结果在lPath中,lPath[0][i]为结点NodeID1到结点i的最短路径长度,lPath[1][i]~lPath[a][i]为最短路径所经过的结点.
//一次可以找出NodeID1到其它所有结点的最短路径.
//Graph[N][N]为图的代权邻接矩阵
}
#4
这个题很easy码
不久使用Dijkstra算法吗！
不久使用Dijkstra算法吗！
#5
谢谢redleave的回答。你的程序我还没来的及看。
这和dijkstra基本没有关系。 可以理解为一维的点。 要求是最短路径最多。 从第一个点到最后一个点，途中经过的点任意。 每两点间的距离也任意。 我不太明白如何才能让最短路径最多，到底多少算是最多
这和dijkstra基本没有关系。 可以理解为一维的点。 要求是最短路径最多。 从第一个点到最后一个点，途中经过的点任意。 每两点间的距离也任意。 我不太明白如何才能让最短路径最多，到底多少算是最多
#6
我的看法：
遍歷所有的點，从第一个点到N个点，让最短路径最多，這些點該由多個正方形或正方體構成。
下面C++程序我可沒測試過，不過我想它是正確的。
#include <algorithm.h>
#include <assert.h>
unsigned int Distance(POINT *P1,POINT *P2);//該函數返回兩點間的距離。
//POINT結構與 Distance方法，該由使用者定義。
unsigned int HowManyPath(POINT *P,unsigned int &n,int *MinPath)
{int *Path,MinDistance=0,CountPath = 1,K=0;
unsigned int *Tmp;
assert(n>2);
Path = new int[(n-1)*n*n];//路徑 這里分配很大內存:n*n*n保存所有路徑
Tmp = new unsigned int[(n-1)*n];//長度,
if(!Path || !Tmp) return 0; //內存分配失敗。
for(int i = 0;i<n;i++) Path[i]=i;
for(int i = 0;i<n;i++) Tmp[i] =0;
for(int x = 1;x<n-1;x++)
for(int y = 1;y<n-1;y++)
{for(int z = 1;z<n-1;z++) if(Path[z] == y) swap(Path[x],Path[z]);
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
if(MinDistance > Tmp[K]) MinDistance = Tmp[K];
++K;
}
for(int i = 0;i<K;i++) if(MinDistance == Tmp[i]) ++CountPath;
MinPath = new int[n*CountPath] ; //返回全部最短路徑
int J=0;
for(int i = 0;i<K;i++)
if(MinDistance == Tmp[i])
{memcpy(&MinPath[J],&Path[(i+1)*n],sizeof(int)*n); //最短路徑
J += n;
}
delete Path;
delete Tmp;
n = CountPath; //返回最短路徑數量
return MinDistance; //返回最短長度
}
遍歷所有的點，从第一个点到N个点，让最短路径最多，這些點該由多個正方形或正方體構成。
下面C++程序我可沒測試過，不過我想它是正確的。
#include <algorithm.h>
#include <assert.h>
unsigned int Distance(POINT *P1,POINT *P2);//該函數返回兩點間的距離。
//POINT結構與 Distance方法，該由使用者定義。
unsigned int HowManyPath(POINT *P,unsigned int &n,int *MinPath)
{int *Path,MinDistance=0,CountPath = 1,K=0;
unsigned int *Tmp;
assert(n>2);
Path = new int[(n-1)*n*n];//路徑 這里分配很大內存:n*n*n保存所有路徑
Tmp = new unsigned int[(n-1)*n];//長度,
if(!Path || !Tmp) return 0; //內存分配失敗。
for(int i = 0;i<n;i++) Path[i]=i;
for(int i = 0;i<n;i++) Tmp[i] =0;
for(int x = 1;x<n-1;x++)
for(int y = 1;y<n-1;y++)
{for(int z = 1;z<n-1;z++) if(Path[z] == y) swap(Path[x],Path[z]);
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
if(MinDistance > Tmp[K]) MinDistance = Tmp[K];
++K;
}
for(int i = 0;i<K;i++) if(MinDistance == Tmp[i]) ++CountPath;
MinPath = new int[n*CountPath] ; //返回全部最短路徑
int J=0;
for(int i = 0;i<K;i++)
if(MinDistance == Tmp[i])
{memcpy(&MinPath[J],&Path[(i+1)*n],sizeof(int)*n); //最短路徑
J += n;
}
delete Path;
delete Tmp;
n = CountPath; //返回最短路徑數量
return MinDistance; //返回最短長度
}
#7
唉，剛貼上去就看到了一處錯誤:
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
應修改如下：
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+Path[i]-1,P+Path[i]);
如果錯誤太多，當我沒說，對不起了。
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
應修改如下：
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+Path[i]-1,P+Path[i]);
如果錯誤太多，當我沒說，對不起了。
#8
K--短路问题!
#9
upup
#10
K--短路问题:扫除法,扩展的Ford法...
#1
upup
#2
是一维的点还是二位三维的点，是不是需要经过其他的点，可不可以重复经过某些点？你的问题说得不清不楚，请说明白一点
#3
这个程序我写了很久了,而且还是从我写的图类中截取出来的,可能有些地方不太对,不过算法的思想还可以看出来,你要的功能只要改一下就可以了.如果你想要我的可以运行的源程序的话,我可以EMAIL给你.不过它没有注释哟!另外,这个算法在数据结构的书中有源程序的,你可以找一本来看看.
int ShortPath(unsigned long NodeID1)
{
NType lPath[N][N];//建立路径表;N为结点数,NType为表中元素的类型
//初始化路径表
memset(lPath,-1, N^N*Sizeof(NType));
for (long i=0;i<N;i++)
{
lPath[0][i]=Graph[NodeID1][i];
if (lPath[0][i])
lPath[1][i]=i;
}
//搜索最短路径
for (long i=1;i<N;i++)
for (long j=0;j<N;j++)
{
long ttt=lPath[i][j];
if (ttt>=0)
for (long p=0;p<N;p++)
if (Graph[ttt][p]>0&&lPath[0][ttt]>0&&(lPath[0][p]==0||Graph[ttt][p]+lPath[0][ttt]<lPath[0][p]))
{
lPath[0][p]=Graph[ttt][p]+lPath[0][ttt];
for(long k=1;k<=i;k++)
lPath[k][p]=lPath[k][ttt];
lPath[i+1][p]=p;
}
}
//搜索的结果在lPath中,lPath[0][i]为结点NodeID1到结点i的最短路径长度,lPath[1][i]~lPath[a][i]为最短路径所经过的结点.
//一次可以找出NodeID1到其它所有结点的最短路径.
//Graph[N][N]为图的代权邻接矩阵
}
int ShortPath(unsigned long NodeID1)
{
NType lPath[N][N];//建立路径表;N为结点数,NType为表中元素的类型
//初始化路径表
memset(lPath,-1, N^N*Sizeof(NType));
for (long i=0;i<N;i++)
{
lPath[0][i]=Graph[NodeID1][i];
if (lPath[0][i])
lPath[1][i]=i;
}
//搜索最短路径
for (long i=1;i<N;i++)
for (long j=0;j<N;j++)
{
long ttt=lPath[i][j];
if (ttt>=0)
for (long p=0;p<N;p++)
if (Graph[ttt][p]>0&&lPath[0][ttt]>0&&(lPath[0][p]==0||Graph[ttt][p]+lPath[0][ttt]<lPath[0][p]))
{
lPath[0][p]=Graph[ttt][p]+lPath[0][ttt];
for(long k=1;k<=i;k++)
lPath[k][p]=lPath[k][ttt];
lPath[i+1][p]=p;
}
}
//搜索的结果在lPath中,lPath[0][i]为结点NodeID1到结点i的最短路径长度,lPath[1][i]~lPath[a][i]为最短路径所经过的结点.
//一次可以找出NodeID1到其它所有结点的最短路径.
//Graph[N][N]为图的代权邻接矩阵
}
#4
这个题很easy码
不久使用Dijkstra算法吗！
不久使用Dijkstra算法吗！
#5
谢谢redleave的回答。你的程序我还没来的及看。
这和dijkstra基本没有关系。 可以理解为一维的点。 要求是最短路径最多。 从第一个点到最后一个点，途中经过的点任意。 每两点间的距离也任意。 我不太明白如何才能让最短路径最多，到底多少算是最多
这和dijkstra基本没有关系。 可以理解为一维的点。 要求是最短路径最多。 从第一个点到最后一个点，途中经过的点任意。 每两点间的距离也任意。 我不太明白如何才能让最短路径最多，到底多少算是最多
#6
我的看法：
遍歷所有的點，从第一个点到N个点，让最短路径最多，這些點該由多個正方形或正方體構成。
下面C++程序我可沒測試過，不過我想它是正確的。
#include <algorithm.h>
#include <assert.h>
unsigned int Distance(POINT *P1,POINT *P2);//該函數返回兩點間的距離。
//POINT結構與 Distance方法，該由使用者定義。
unsigned int HowManyPath(POINT *P,unsigned int &n,int *MinPath)
{int *Path,MinDistance=0,CountPath = 1,K=0;
unsigned int *Tmp;
assert(n>2);
Path = new int[(n-1)*n*n];//路徑 這里分配很大內存:n*n*n保存所有路徑
Tmp = new unsigned int[(n-1)*n];//長度,
if(!Path || !Tmp) return 0; //內存分配失敗。
for(int i = 0;i<n;i++) Path[i]=i;
for(int i = 0;i<n;i++) Tmp[i] =0;
for(int x = 1;x<n-1;x++)
for(int y = 1;y<n-1;y++)
{for(int z = 1;z<n-1;z++) if(Path[z] == y) swap(Path[x],Path[z]);
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
if(MinDistance > Tmp[K]) MinDistance = Tmp[K];
++K;
}
for(int i = 0;i<K;i++) if(MinDistance == Tmp[i]) ++CountPath;
MinPath = new int[n*CountPath] ; //返回全部最短路徑
int J=0;
for(int i = 0;i<K;i++)
if(MinDistance == Tmp[i])
{memcpy(&MinPath[J],&Path[(i+1)*n],sizeof(int)*n); //最短路徑
J += n;
}
delete Path;
delete Tmp;
n = CountPath; //返回最短路徑數量
return MinDistance; //返回最短長度
}
遍歷所有的點，从第一个点到N个点，让最短路径最多，這些點該由多個正方形或正方體構成。
下面C++程序我可沒測試過，不過我想它是正確的。
#include <algorithm.h>
#include <assert.h>
unsigned int Distance(POINT *P1,POINT *P2);//該函數返回兩點間的距離。
//POINT結構與 Distance方法，該由使用者定義。
unsigned int HowManyPath(POINT *P,unsigned int &n,int *MinPath)
{int *Path,MinDistance=0,CountPath = 1,K=0;
unsigned int *Tmp;
assert(n>2);
Path = new int[(n-1)*n*n];//路徑 這里分配很大內存:n*n*n保存所有路徑
Tmp = new unsigned int[(n-1)*n];//長度,
if(!Path || !Tmp) return 0; //內存分配失敗。
for(int i = 0;i<n;i++) Path[i]=i;
for(int i = 0;i<n;i++) Tmp[i] =0;
for(int x = 1;x<n-1;x++)
for(int y = 1;y<n-1;y++)
{for(int z = 1;z<n-1;z++) if(Path[z] == y) swap(Path[x],Path[z]);
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
if(MinDistance > Tmp[K]) MinDistance = Tmp[K];
++K;
}
for(int i = 0;i<K;i++) if(MinDistance == Tmp[i]) ++CountPath;
MinPath = new int[n*CountPath] ; //返回全部最短路徑
int J=0;
for(int i = 0;i<K;i++)
if(MinDistance == Tmp[i])
{memcpy(&MinPath[J],&Path[(i+1)*n],sizeof(int)*n); //最短路徑
J += n;
}
delete Path;
delete Tmp;
n = CountPath; //返回最短路徑數量
return MinDistance; //返回最短長度
}
#7
唉，剛貼上去就看到了一處錯誤:
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
應修改如下：
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+Path[i]-1,P+Path[i]);
如果錯誤太多，當我沒說，對不起了。
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+i-1,P+i);
應修改如下：
memcpy(&Path[x*n],&Path[0],sizeof(int)*n);
for(int i = 1;i<n;i++) Tmp[K] += Distance(P+Path[i]-1,P+Path[i]);
如果錯誤太多，當我沒說，對不起了。
#8
K--短路问题!
#9
upup
#10
K--短路问题:扫除法,扩展的Ford法...