首先说一下什么叫单源最短路径问题：

给定一个带权有向图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