前言：
现时朋友们对“dijkstra算法图示”大体比较看重，看官们都需要分析一些“dijkstra算法图示”的相关文章。那么小编也在网上收集了一些关于“dijkstra算法图示””的相关资讯，希望小伙伴们能喜欢，姐妹们一起来学习一下吧！用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。 Dijkstra的时间复杂度是O (N2)，它不能处理存在负边权的情况。 算法描述： 设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。 a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; b)For (i = 1; i <= n ; i++) 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。 2.u标记为已确定最短路径 3.For 与u相连的每个未确定最短路径的顶点v if (dis[u]+w[u][v] < dis[v]) { dis[v] = dis[u] + w[u][v]; pre[v] = u; } c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。 算法分析&思想讲解： 从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2。特殊地，我们认为起点1也是一个“中转点”）。显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2 的最短路径后，才能求出从起点到5的最短路径）。 换句话说，如果起点1到某一点V0的最短路径要经过中转点Vi，那么中转点Vi一定是先于V0被确定了最短路径的点。
算法开始时，作为起点的dis[1] = 0，其他的点dis[i] = 0x7fffffff。
接下来的两轮循环将4、5也变成白点。N轮循环结束后，所有的点的最短路径即能求出。 Dijkstra无法处理边权为负的情况，例如右图这个例子。 2到3的边权值为-4，显然从起点1到3的最短路径是-2（1→2→3），但是dijskstra在第二轮循环开始时会找到当前dis[i]最小的点3，并标记它为白点。 这时的dis[3]=1，然而1却不是从起点到点3的最短路径。因为3已被标记为白点，最短路径值dis[3]不会再被修改了，所以我们在边权存在负数的情况下得到了错误的答案！
next数组版+堆优化O(nlogn)
标签： #dijkstra算法图示 #dijkstra算法程序 #dijkstra算法步骤例题表格 #c语言dijkstra算法 #算法o
