dijkstra算法
我们先来思考一个问题:当给我们一张地图时,地图上有许多的城市,城市之间连接着长度不同的道路,问你从1号城市到第n号城市的最短路径怎么办呢?
这里每条边的权重不为1,所有不可以采用bfs的方法求最短路,这里我们引入dijkstra算法求最短路.
一.什么是dijkstra算法: 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止
二.贪心的理解:我们每一步都找到与1最近的点,用这个点来更新其他的点,那么更新完成之后的这个点就一定是最短距离(上次重复这个操作的时候就已经把比它离1距离更短的点更新完成了),也可以理解为数学研究中的数学归纳法.
三.代码的实际写法:我们始终是要找的是n号点离原点的最短距离,所以我们用dist[]表示每一个点到1的距离,规定dist[1]=0,因为1到1距离为0,然后再每次更新的时候取dist[x] = min(dist [x],dist [y]+d [y] [x]),这里的d [y] [x]是y到x的距离,所以dist[x]应该是在它本身离1的距离与(y到1的距离+y到x的距离)取最小值.
那么接下来就是代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 550;
int dg[N][N],dist[N];//dg[i][j]表示i点到j点的距离
bool st[N];//标记已经找到的最短距离
int n,m;
void dijkstra()
{
memset(dist,0x3f3f3f3f,sizeof(dist));//每个点到1的距离初始化为正无穷
dist[1]=0;
for(int i = 1;i <= n;i ++ ){
int t = -1;
for(int j = 1;j <= n;j ++ )
if(!st[j] && (t==-1 || dist[t]>dist[j]))//首先要是不在已经找完的集合离,其次是要找到最短路径的点
t=j;
st[t]=true;//标记它为已经找到最短路径的点,把他放入集合当中去
for(int j = 1;j <= n;j ++ )
dist[j]=min(dist[j],dist[t]+dg[t][j]);//用这一点更新每一个点
}
if(dist[n]==0x3f3f3f3f) cout<<-1<<endl;说明1与n之间没有路径,所以是正无穷,输出-1
else cout<<dist[n]<<endl;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++ )
for(int j = 1;j <= n;j ++ )
dg[i][j]=0x3f3f3f3f; //初始化正无穷
while(m--)
{
int a,b,val;
cin >> a >> b >> val;
dg[a][b]=min(dg[a][b],val);//有重复的边,取最小值
}
dijkstra();
return 0;
}