（复习）图论--最短路--Dijkstra算法
定义：迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
思路：选一起点（单源问题中的源点），从起点开始拓展，用边更新每一个点到起点的最小距离，每次选一个到起点距离最短的点进行下一步拓展。
【（复习）图论--最短路--Dijkstra算法】代码：
/*
2016.8.7 BulaBulaCHN
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Edge
{
int from,to;
int val,next;
}eage[100005];
int tot=0;
int head[1005];
void add(int x,int y,int z)
{
eage[++tot].from=x;
eage[tot].to=y;
eage[tot].val=z;
eage[tot].next=head[x];
head[x]=tot;
}
int n,m;
int que[1005];
bool book[1005];
int dis[1005];
int top=0,tail=0;
int main()
{
freopen("textdata.in","r",stdin);
freopen("textdata.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;
i<=m;
i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for(int i=1;
i<=n;
i++) dis[i]=9999999;
dis[1]=0;
que[++tail]=1;
book[1]=1;
for(int i=head[1];
i;
i=eage[i].next)
{
dis[eage[i].to]=eage[i].val+dis[1];
}
while(1)
{
int point=-1;
int mmin=9999999;
for(int i=1;
i<=n;
i++)
if(dis[i] 推荐阅读
- JS中的各种宽高度定义及其应用
- 祖母走了
- 唯独你最得我意
- 人生感悟记＃环境仪器宋庆国成长记＃072
- 危险也是机会
- “精神病患者”的角度问题
- 对抗抑郁最好的方法
- 小学英语必考的10个知识点归纳，复习必备！
- 放下心中的偶像包袱吧
- 怎样用黑谜速冻膜去黑头，|怎样用黑谜速冻膜去黑头， 最有效的去黑头的方法看这!