dijkstra
本文转载自：https://blog.csdn.net/lbperfect123/article/details/84281300
dijkstra算法
dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
问题引入：
指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。
下面我们来模拟一下：
模板
#include<stdio.h>
#include<string.h>
const int inf=0x3f3f3f3f;
int ma[1005][1005];
int dis[1005];
bool vis[1005];
int t,n;
void Dijk()
{
for(int i=0;i<n-1;i++)//遍历除了n本身以外的n-1个城市，这里的i不代表城市，仅代表遍历n-1次
{
int min=inf,k;//k用来存储最小的且没被松弛过的城市
for(int j=1;j<=n;j++)
{
if(min>dis[j]&&!vis[j]) //依次比较
{
min=dis[j];
k=j;//记录最小且没被松弛过的城市的下标
}
}
vis[k]=1;//标记被松弛过的城市
for(int h=1;h<=n;h++)
{
if(dis[h]>dis[k]+ma[k][h])
dis[h]=dis[k]+ma[k][h];
}
}
}
int main()
{
scanf("%d%d",&t,&n);
int a,b,c;
memset(ma,inf,sizeof(ma));//初始化ma数组
for(int i=1;i<=n;i++)
ma[i][i]=0;
memset(vis,0,sizeof(vis));//初始化vis数组
vis[n]=1;
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
if(ma[a][b]>c)//可能会有已经有的路径长度，但是新的长度大于原有的，所以需要判断
ma[a][b]=ma[b][a]=c;
}
for(int i=1;i<=n;i++)//初始化dis数组
dis[i]=ma[n][i];
Dijk();
printf("%d\n",dis[1]);
return 0;
}
相关阅读
洗牌算法洗牌算法是常见的随机问题：将1 ～ 52张扑克牌重新洗牌什么是好的洗牌算法：洗牌之后，如果能够保证每一个数出现在所有位置上的
下面用通俗易懂的话来概述一下： 指针-对于一个类型T，T*就是指向T的指针类型，也即一个T*类型的变量能够保存一个T对象的地址，而类型T是
1. 原理 用meanshift做图像平滑和分割，其实是一回事。其本质是经过迭代，将收敛点的像素值代替原来的像素值，从而去除了局部相似的纹
Serverlet 动态web资源详解（包含生命周期等） no 10.
前言：web资源有两种分类：*静态资源HTML ，JavaScript*动态资源Java server pages ，Serverletserverlet介绍 作用： 访问静态资源或者动态
前提 在对象拷贝过程中，如果没有自定义拷贝构造函数，系统会提供一个缺省的拷贝构造函数，缺省的拷贝构造函数对于基本类型的成员变量