首先说一下什么叫单源最短路径问题： 给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。（摘自百科）  这个题算是正儿八经的单源最短路径问题，因为图中边上的权值不可能为负值，所以采用dijkstra算法： dijkstra算法采用贪心策略，下面进行图解 准备：我们需要一个b数组作为一个集合用来表示已经达到最优的点，b[i]=0表示编号为i的点在集合外； 一个dis数组表示距离，dis【i】表示出发点到i的最短距离，dis初始化为-1； 1，b【1】=1（1到1距离为0，已达到最优），然后从出发点点1开始找到目标点能到达的点2,3并更新dis数组； 从中选择距离出发点最近的点3（即从b数组为0，d值最小且不为0的点中选一个点）； 2，b【3】=1，从能从3到达的b【i】=0的点中进行下一步操作；分两种情况，dis为-1和不为-1；如点5的dis值为-1，辣么d[5]=map[5][3]+d[3]=10+1=11;  如dis[2]=4,dis[2]=min(dis[2],map[2][3],+d[3])=min(4,5)=4; 目的就是利用第1，步找到的距离目标点最近的点来尝试优化当前的路径； 3，从b数组为0，d值最小且不为0的点中选一个点（1,3 b数组值已为1），选出点2； 4，重复第二步b【2】=1； 从能从3到达的b【i】=0的点中进行下一步操作；分两种情况，dis为-1和不为-1；如点4的dis值为-1，辣么d[4]=map[4][2]+d[2]=2+4=6;  如dis[5]=11,dis[5]=min(dis[5],map[2][5],+d[2])=min(11,1+4)=5; 直到所有的点b数组值为1，输出dis数组就是初始点到每一个点的最近路径长度 理解了大概的dijkstra算法思路，下面在具体的题目中进行实践，耐心看完才能有收获(〃''〃) 下面在题目中进行讲解： 条件贼多的题>_< 在AC代码中解释 #include #include #include #include using namespace std; const int L=110; int C[L],vis[L][L],map[L][L],dis[L];// 文化值数组，文化是否冲突数组 地图  出发点到每个点的最短距离数组  bool b[L]; // 点是否最优判断数组  int main(){ memset(map,0,sizeof(map)); int N,K,M,S,T; cin>>N>>K>>M>>S>>T; for(int i=1;i<=N;i++)cin>>C[i]; for(int i=1;i<=K;i++)for(int n=1;n<=K;n++)cin>>vis[i][n]; for(int i=1;i<=M;i++){ int x,y,d; cin>>x>>y>>d; map[x][y]=d; map[y][x]=d; } memset(dis,-1,sizeof(dis)); //数据初始化 for(int i=1;i<=N;i++){ if(i==S)dis[i]=0; else if(map[S][i]!=0){ if(vis[C[i]][C[S]]==0)dis[i]=map[S][i];//初始化  } } b[S]=1;// 初始化  for(int i=1;i< p=""> int xmin=INT_MAX,k=-1; for(int n=1;n<=N;n++)if(!b[n]&&xmin>dis[n]&&dis[n]!=-1){ xmin=dis[n]; k=n; //挑出的最近的点  } if(k==-1)continue; //利用挑出的点进行优化  b[k]=1; for(int n=1;n<=N;n++)if(!b[n]&&map[n][k]!=0&&vis[C[n]][C[k]]==0){ if(dis[n]==-1)dis[n]=dis[k]+map[n][k]; else dis[n]=min(dis[n],dis[k]+map[n][k]); } } cout<<dis[t];< p=""> return 0; } 

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com