求有向图中任意两个顶点的最短路径---dijkstra算法

    这是图论里的入门算法，但又有实力不够，因此困扰了我许久，在网上也学习了很多大牛的解题思路，我也有所感悟，简单记录下，帮助自己，也希望让更多的学会，我这里只写代码，算法思想可以去其他博主那里学习，这个代码比较简短，希望大家学会，对竞赛友友也有帮助的呦！

直接上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int mp[N][N];//地图
int dis[N];//距离数组
int vis[N];//标记数组
int n,m,start,end;//顶点数，边数，起始点，终点
int dijkstra(){
	for(int i=1;i<=n;i++){//第一个for:控制循环次数
		int index=-1;//保存所找到的点
		for(int j=1;j<=n;j++){//第二个for:找出距离源点最近的点
			if(!vis[j]&&(index==-1||dis[j]<dis[index])){
				index=j;
			}
		}
		for(int j=1;j<=n;j++){//更新dis数组
			dis[j]=min(dis[j],dis[index]+mp[index][j]);
		}
		vis[index]=1;//标记改点，表示已访问过
	}
	if(dis[end]!=0x3f3f3f3f){
		return dis[end];
	}else{
		return -1;
	}
}
int main(){
	memset(mp,0x3f,sizeof(mp));//memset函数包含在<string.h>头文件里，挺好用，大家自行学习
	memset(dis,0x3f,sizeof(dis));
	cout<<"请输入点数 边数 起点 终点:"<<endl;
	cin>>n>>m>>start>>end;
	int tmp=m;//记录边的次数
	while(tmp--){
		int a,b,w;//起点，终点，权值
		cin>>a>>b>>w;
		mp[a][b]=(w<mp[a][b]?w:mp[a][b]);//三目运算符，有重复的边选择更短的
	}
	
	for(int i=1;i<=n;i++){
		if(mp[start][i]!=0x3f3f3f3f){
			dis[i]=mp[start][i];
		}
	}
	dis[start]=0;
	int len=dijkstra();
	cout<<len;
	return 0;
} 

测试用例

6 8 3 6
3 2 4
3 1 8
3 1 2
2 4 2
4 5 1
5 6 1
1 5 4
1 6 10

//运行结果为 7

代码哪里有问题随时私信我，一定及时更改。

感谢大家浏览！！！