13518219792
一、用途
目前成都创新互联已为1000+的企业提供了网站建设、域名、虚拟主机、网站托管维护、企业网站设计、尼金平网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。Dijkstra算法是求最短路的方法之一，要求题目中边的权重都为非负数才可使用。目前有两种Dijkstra算法模板。
//下面n代表点数，m代表边数。
1.朴素版Dijkstra算法：时间复杂度O（n^2），适用于稠密图（点少边多），n^2和m是一个量级的。
面对稠密图我们使用的是邻接矩阵来存储信息。g[N][N]=W。W指的是权重。
例：g[a][b]=5,说明a到b的距离是5。
2.堆优化版Dijkstra算法：时间复杂度O（mlogn），适用于稀疏图（边和点差不多），m远小于n^2.
面对稀疏图我们使用邻接表来储存信息。
二、算法如何使用。
1.第一步：创建dist[N]数组来存储，第i个点到1号点的距离。初始时dist定义为无穷大，但dist[1]=0;
2.第二步：创建st[N]数组来存储已经找到最短路的点。st[i]为真，说明该点到1号点的最短距离已确定。若为假，则说明还未确定最短路径。初始化时，数组中各个元素为假。
3.第三步：遍历dist[N]数组，找到没有确定最短路径的节点中距离1号点最近的点。简单来说就是，找到一个不在st[N]数组里并且距离1号点最近的点。（暂且把这点叫做i点）
这样一来，i点的最短距离就确定了。（此处的i点的最短距离一定等于dist[i]，这有关Dijkstra算法的数学原理，有兴趣可以查查）
既然i点最短距离确定了，自然要将i点放到st[N]数组里去了。
4.第四步：运用找到的i点，去更新所有点的最短距离。
代码：for(int j=1;j<=n;j++)
dist[j]=min(dist[i],g[i][j]);
5.第五步：重复三、四步骤n-1次，则所有的点都可以找到最短路径。（因为每一次都会找到一个i点，并将它放进st[N]数组，重复n-1次就确定了所有的点）
三、举个简单例子
如下图：
1. 先开始，所有点都没有找到最短距离所以st[N]所有元素都是false，除1号点外，其他的距离全是∞。
找到距离1号点最近，且不在st[N]数组内的点，发现1号点就是要找的点。因为dist[1]最小，并且st[1]=false。
所以用1号点去更新所有的点距离。
dist[2]=min(dist[2],dist[1]+g[1][2]);
dist[3]=min(dist[3],dist[1]+g[1][3]);
2.此时变成了
重复步骤，找到距离1号点最近，且不在st[N]数组内的点，发现2号点是我们要找的。
所以用2号点更新所有点的距离。
dist[1]=min(dist[1],dist[2]+g[2][1]);
dist[3]=min(dist[3],dist[2]+g[2][3]);
3.得到最终结果
四、例题
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1号点到 n 号点的最短距离，如果无法从 1号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500
1≤m≤100000,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4输出样例：
3五、例题题解
重边和自环如何解决？
1.重边：我们可以取重边中最小的一条边。g[a][b]=min(g[a][b],c)；
2.自环：本题对自环没有影响，因为dist[j]=min(dist[j],dist[t]+g[t][j]);
t==j时g[j][j]，代表的就是自环，只要自环是非负的，dist[j]的值就不会改变。
代码:
#include
#include
#include
using namespace std;
const int N=510;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N]; //用于记录每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定
int n,m;
int Dijkstra()
{
memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大
dist[1]=0; //第一个点到自身的距离为0
for(int i=0;i
int t=-1; //t存储当前访问的点
for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始
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]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径
//所以每个点初始为无限大
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边
}
cout<
}
借用一下Acwing平台上yxc大佬的代码。。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
