迪杰斯特拉（Dijkstra)算法

全知识整理目录

数据结构整理的目录包括了许多的数据结构相关知识。

目录

概述

算法过程

代码

总结

概述

什么是Dijkstra？

Dijkstra算法是朴素算法，朴素是体现在其算法思想上。

每一次都，从可以到达的边当中，选择最短的一条边，以此连接整个图，达到寻求最短路径的效果。

算法过程

如下图，第一次从源点出发，能够到达的顶点只有1，2，3那么到这3个顶点的路径中，选择最小的一个，进行连接，以此类推。

这之中就不得不介绍一个dist数组了。这也是Dijkstra算法的核心，而dist数组就是实时记录当前可达最短边，当有更短的路线就更新。

---

下面是平板手写的，可能看起来舒服一点，更新一下。

---

下面是第一次，本上和口诉的。 

 dist数组为

 

而Dijkstra算法代码最重要的部分是，第一个for循环用来寻找最短的边，第二个for循环用来修正最短的边，所以时间复杂度为O（）

代码

#include
using namespace std;
#define nmax 110
#define inf 999999999

int u;
int minx;
for(int i=1;i<=n;i++) dst[i]=edge[1][i];
for(int i=1;i<=n;i++) book[i]=0;
book[1]=1;
for(int i=1;i<=n-1;i++){
        minx=inf;
    for(int j=1;j<=n;j++){
        if(book[j]==0&&dst[j]dst[u]+edge[u][k]&&edge[u][k] 
总结 
记住以下两点，我相信Dijkstra算法的过程和代码都能够理解。
 
Dijkstra算法，的核心是两层for循环，时间复杂度O（）。
过程的核心是，dist数组，dist是实时更新，下一次能够到达的最短路径。 
参考
 
参考博文