dijkstra算法平均最短路径公式

在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。

交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。

以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。

最短路径问题的提法很多。

在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。

例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：图G14从有向图可看出，顶点v1到v4的路径有3条：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4)，其路径长度分别为：15,20和10。

因此v1到v4的最短路径为(v1,v3,v2,v4 )。

为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。

那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。

迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E)，其中，V={0,2,…,n-1}，cost是表示G的邻接矩阵，G.arcs [i][j] .adj 表示有向边<i,j>的权。

若不存在有向边<i,j>，则G.arcs [i][j] .adj 的权为无穷大(这里取值为32767)。

设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。

设顶点v0为源点，集合S的初态只包含顶点v0。

数组D记录从源点到其他各顶点当前的最短距离，其初值为D[i]= G.arcs[v0][i].adj ，i=1,…,n-1。

从S之外的顶点集合V-S 中选出一个顶点w，使D[w]的值最小。

于是从源点到达w只通过S 中的顶点，把w加入集合S中调整D中记录的从源点到V-S中每个顶点v的距离：从原来的D[v] 和D[w]+ G.arcs [w][v] .adj中选择较小的值作为新的D[v]。

Dijkstra算法Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。

注意该算法要求图中不存在负权边。

function [S,D]=minRoute(i,m,W)%图与网络论中求最短路径的Dijkstra算法M-函数%格式[S,D]=minroute(i,m,W)% i为最短路径的起始点,m为图顶点数,W为图的带权邻接矩阵，% 不构成边的两顶点之间的权用inf表示。

显示结果为：S的每% 一列从上到下记录了从始点到终点的最短路径所经顶点的序号；% D是一行向量，记录了S中所示路径的大小;%例如% clear;w=inf*ones(6);w(1,3)=10;w(1,5)=30;% w(1,6)=100;w(2,3)=5;w(3,4)=50;w(4,6)=10;% w(5,4)=20;w(5,6)=60;% i=1;[s,d]=minroute(i,6,w)dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];% dd的第二行是每次求出的最短路径的终点，第一行是最短路径的值kk=2;[mdd,ndd]=size(dd);while ~isempty(V)[tmpd,j]=min(W(i,V));tmpj=V(j);for k=2:ndd[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];endtmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));if tmp3==tmpd, ss(1:2,kk)=[i;tmp(tmp4,2)];else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);if dd(2,tmp4)==ss(tmp6,tmp4)ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];else, ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)]; end;enddd=[dd,[tmp3;tmp(tmp4,2)]];V(tmp(tmp4,3))=[]; [mdd,ndd]=size(dd);kk=kk+1;end; S=ss; D=dd(1,:);。

⼀步⼀步深⼊理解Dijkstra算法先简单介绍⼀下最短路径：最短路径是啥？就是⼀个带边值的图中从某⼀个顶点到另外⼀个顶点的最短路径。

官⽅定义：对于内⽹图⽽⾔，最短路径是指两顶点之间经过的边上权值之和最⼩的路径。

并且我们称路径上的第⼀个顶点为源点，最后⼀个顶点为终点。

由于⾮内⽹图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径。

我们时常会⾯临着对路径选择的决策问题，例如在中国的⼀些⼀线城市如北京、上海、⼴州、深圳等，⼀般从A点到到达B点都要通过⼏次地铁、公交的换乘才可以到达。

有些朋友想⽤最短对的时间，有些朋友想花最少的⾦钱，这就涉及到不同的⽅案，那么如何才能最快的计算出最佳的⽅案呢？最短路径求法在⽹图和⾮⽹图中，最短路径的含义是不同的。

⽹图是两顶点经过的边上权值之和最少的路径。

⾮⽹图是两顶点之间经过的边数最少的路径。

我们把路径起始的第⼀个顶点称为源点，最后⼀个顶点称为终点。

关于最短路径的算法，我们会介绍以下算法：迪杰斯特拉算法（Dijkstra）求V0到V8的最短路径你找到了吗好了，我想你⼤概明⽩了，这个迪杰斯特拉算法是如何⼯作的。

它并不是⼀下⼦就求出了V0到V8的最短路径，⽽是⼀步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

迪杰斯特拉(Dijkstra)算法1. 迪杰斯特拉(Dijkstra)算法简介迪杰斯特拉（dijkstra）算法是典型的⽤来解决最短路径的算法，也是很多教程中的范例，由荷兰计算机科学家狄克斯特拉于1959年提出，⽤来求得从起始点到其他所有点最短路径。

该算法采⽤了贪⼼的思想，每次都查找与该点距离最近的点，也因为这样，它不能⽤来解决存在负权边的图。

解决的问题⼤多是这样的：有⼀个⽆向图G(V,E)，边E[i]的权值为W[i]，找出V[0]到V[i]的最短路径。

2.迪杰斯特拉算法的原理(附上⼩图⼀张)①⾸先，引⼊⼀个辅助向量D，它的每个分量D[i]表⽰当前所找到的 Dijkstra算法运⾏动画过程 Dijkstra算法运⾏动画过程从起始点（即源点）到其它每个顶点的长度。

图的最短路径——dijkstra算法和Floyd算法dijkstra算法 求某⼀顶点到其它各个顶点的最短路径；已知某⼀顶点v0，求它顶点到其它顶点的最短路径，该算法按照最短路径递增的顺序产⽣⼀点到其余各顶点的所有最短路径。

对于图G={V,{E}};将图中的顶点分为两组: 第⼀组S：求出已知顶点的最短路径的集合 第⼆组V-S：尚未求出最短路径的顶点集合（开始为V-{v0}的全部顶点）该算法将最短路径以递增顺序逐个将第⼆组顶点加⼊到第⼀组顶点中，直到所有的顶点都被加⼊到第⼀组顶点集S为⽌。

dijkstra算法和最⼩⽣树中的prim算法类似，都是把顶点看做集合，向所求集合中加点#include <iostream>#include <vector>#include <algorithm>using namespace std;const int INF=0x3f3f;class Graph{private:int num;int e;vector<vector<int> > arr;//存储图的邻接矩阵vector<bool> visit;//标记该结点是否⽤过vector<int> path;//从v0到其他结点的最短路径public:Graph();void dijkstra(const int &i);};Graph::Graph(){cout<<" num"<<endl;cin>>num;cout<<" e"<<endl;cin>>e;visit.resize(num,false);path.resize(num);arr.resize(num);for(int i=0;i<num;++i)arr.at(i).resize(num,INF);cout<<" 边的起始点和终点&&权值"<<endl;pair<int,int> p;for(int i=0;i<e;++i){cin>>p.first>>p.second;cin>>arr.at(p.first-1).at(p.second-1);}}void Graph::dijkstra(const int &index){//⾸先存储的是index结点到其他节点的最短路径的值for(int i=0;i<num;++i)path.at(i)=arr.at(index-1).at(i);//初始化visitvisit.at(index-1)=true;for(int check=0;check<num-1;++check){int Min=INF,flag=0;for(int i=0;i<num;++i){if(!visit.at(i)&&path.at(i)<Min){flag=i;Min=path.at(i);}}visit.at(flag)=true;for(int i=0;i<num;++i)//如果由于v0结点的加⼊导致index结点到其它接点的值变⼩更新path{if(path.at(i)>path.at(flag)+arr.at(flag).at(i))path.at(i)=path.at(flag)+arr.at(flag).at(i);}}for(int i=0;i<num;++i)cout<<path.at(i)<<"\t";cout<<endl;}int main(){Graph g;g.dijkstra(1);return0;}floyd算法 如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引⼊第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。

修路问题公式修路问题，也被称为最短路径问题，是指给定一个连通图，其中各个节点之间有边连接，每条边都带有一个权重（或距离），要求在图中找到一条路径，使得起点到终点的路径长度最短。

最常用的解决修路问题的算法是Dijkstra算法和A*算法。

1. Dijkstra算法：Dijkstra算法是一种贪心算法，通过动态规划的方式逐步更新起点到各个节点的最短路径。

具体步骤：-初始化一个距离数组，记录每个节点到起点的距离，起点本身的距离为0，其它节点的距离为无穷大。

-标记起点为当前节点，将起点到各个邻接节点的距离更新到距离数组中。

-从距离数组中选择最小距离的节点作为下一个当前节点，并将其标记。

-更新距离数组，如果通过当前节点可以获得更短的路径，则更新路径长度。

-重复上述步骤直到终点被标记为当前节点或所有节点都被标记为当前节点。

-根据最终的距离数组可以得到起点到终点的最短路径。

2. A*算法：A*算法是一种启发式搜索算法，它在Dijkstra算法的基础上引入了每个节点的估计成本，即起点经过该节点到达终点的估计距离。

具体步骤：-初始化一个开放列表，用于存储待探索的节点。

-将起点放入开放列表。

-循环以下步骤，直到开放列表为空或终点被探索到：-从开放列表中选择估计成本最小的节点作为当前节点。

-如果当前节点为终点，则搜索结束。

-将当前节点标记为已探索。

-遍历当前节点的邻居节点：-如果邻居节点已经被标记为已探索，“忽略”该节点。

-如果邻居节点不在开放列表中，加入开放列表，并更新邻居节点的估计成本和父节点。

-如果邻居节点已经在开放列表中，检查经过当前节点到达该邻居节点的路径是否更短。

如果更短，则更新邻居节点的估计成本和父节点。

-根据每个节点的父节点可以得到起点到终点的最短路径。

拓展：修路问题在现实生活中有很多应用，比如城市规划、物流路径规划等。

除了Dijkstra算法和A*算法以外，还有一些其他的算法，如Floyd-Warshall算法、Bellman-Ford算法等，它们也可以用于解决修路问题，但适用的场景或复杂度有所不同。

图解迪杰斯特拉（Dijkstra）最短路径算法目录前言一、最短路径的概念及应用二、Dijkstra迪杰斯特拉1.什么是Dijkstra2.逻辑实现总结前言无论是什么程序都要和数据打交道，一个好的程序员会选择更优的数据结构来更好的解决问题，因此数据结构的重要性不言而喻。

数据结构的学习本质上是让我们能见到很多前辈在解决一些要求时间和空间的难点问题上设计出的一系列解决方法，我们可以在今后借鉴这些方法，也可以根据这些方法在遇到具体的新问题时提出自己的解决方法。

（所以各种定义等字眼就不用过度深究啦，每个人的表达方式不一样而已），在此以下的所有代码都是仅供参考，并不是唯一的答案，只要逻辑上能行的通，写出来的代码能达到相同的结果，并且在复杂度上差不多，就行了。

一、最短路径的概念及应用在介绍最短路径之前我们首先要明白两个概念：什么是源点，什么是终点？在一条路径中，起始的第一个节点叫做源点；终点：在一条路径中，最后一个的节点叫做终点；注意！源点和终点都只是相对于一条路径而言，每一条路径都会有相同或者不相同的源点和终点。

而最短路径这个词不用过多解释，就是其字面意思：在图中，对于非带权无向图而言，从源点到终点边最少的路径（也就是BFS广度优先的方法）；而对于带权图而言，从源点到终点权值之和最少的路径叫最短路径；最短路径应用：道路规划；我们最关心的就是如何用代码去实现寻找最短路径，通过实现最短路径有两种算法：Dijkstra迪杰斯特拉算法和Floyd弗洛伊德算法，接下来我会详细讲解Dijkstra迪杰斯特拉算法；二、Dijkstra迪杰斯特拉1.什么是DijkstraDijkstra迪杰斯特拉是一种处理单源点的最短路径算法，就是说求从某一个节点到其他所有节点的最短路径就是Dijkstra；2.逻辑实现在Dijkstra中，我们需要引入一个辅助变量D（遇到解决不了的问题就加变量[_doge]），这个D我们把它设置为数组，数组里每一个数据表示当前所找到的从源点V开始到每一个节点Vi的最短路径长度，如果V到Vi有弧，那么就是每一个数据存储的就是弧的权值之和，否则就是无穷大；我们还需要两个数组P和Final，它们分别表示：源点到Vi的走过的路径向量，和当前已经求得的从源点到Vi的最短路径（也就是作为一个标记表示该节点已经加入到最短路径中了）；那么对于如下这个带权无向图而言，我们应该如何去找到从V0到V8的最短路径呢；在上文中我们已经描述过了，在从V0到V8的这一条最短路径中，V0自然是源点，而V8自然是终点；于是我根据上文的描述具现化出如下的表格；在辅助向量D中，与源点V0有边的就填入边的权值，没边就是无穷大；构建了D、P和Final，那么我们要开始遍历V0，找V0的所有边中权值最短的的边，把它在D、P、Final中更新；具体是什么意识呢？在上述带权无向图中，我们可以得到与源点有关的边有（V0，V1）和（V0，V2），它们的权值分别是1和5，那么我们要找到的权值最短的的边，就是权值为1 的（V0，V1），所以把Final[1]置1，表示这个边已经加入到最短路径之中了；而原本从V0到V2的距离是5，现在找到了一条更短的从V0 -> V1 -> V2距离为4，所以D[2]更新为4，P[2]更新为1，表示源点到V2经过了V1的中转；继续遍历，找到从V0出发，路径最短并且final的值为0的节点。

求最短路径经典算法详解-迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）什么是“迪杰斯特拉(Dijkstra)”算法？ 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家于1959 年提出的，因此⼜叫。

是从⼀个顶点到其余各顶点的算法。

迪杰斯特拉算法主要特点是以起始点为中⼼向外层层扩展，直到扩展到终点为⽌。

⽤来解决什么样的问题？ 解决的是有权图中最短路径问题，给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径应⽤案例：1.计算机⽹络传输的问题：怎样找到⼀种最经济的⽅式，从⼀台计算机向⽹上所有其它计算机发送⼀条消息。

2.交通运输问题，⾛那条路径最优解决思路步骤 基本思想：设置⼀个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。

以后每求得⼀条最短路径v, …, vk，就将vk加⼊集合S中，并将路径v, …, vk , vi与原来的假设相⽐较，取路径长度较⼩者为最短路径。

重复上述过程，直到集合V中全部顶点加⼊到集合S中。

设计数据结构 : 1、图的存储结构：带权的邻接矩阵存储结构。

2、数组dist[n]：每个分量dist[i]表⽰当前所找到的从始点v到终点vi的最短路径的长度。

初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。

3、数组path[n]：path[i]是⼀个字符串，表⽰当前所找到的从始点v到终点vi的最短路径。

初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。

4、数组s[n]：存放源点和已经⽣成的终点，其初态为只有⼀个源点v。

详细步骤及相关说明迪杰斯特拉算法（详细）Dist ：存储了当前起点到其余各顶点的最短路径长度Path ：存储了起点到其余各顶点的路径Set：标记了哪些顶点已经被选⼊了最短路径说明：+：表⽰起点到顶点没有直接相连-1：当前顶点在其最短路径上⾯没有前⼀个顶点或者没有关系初始状态0123456Dist0466+++Path-1000-1-1-1Set1000000从某个定点到其余各个顶点的最短路径选择距离起点最近的那个顶点，将其并⼊，然后扫描图中未被并⼊顶点的所有顶点。

Dijkstra算法求解单源最短路径问题一、单源最短路径问题描述给定一个带权有向图G=(V,E),其中每条边的权都是非负数。

给定V中的一个顶点，称为源。

计算从源到所有其他定点的最短路径长度。

这里的路径长度就是指各边权之和。

该问题称为单源最短路径问题（Single-Source Shortest Paths）。

二、Dijkstra算法思想将图G中所有的顶点V分成两个顶点集合S和T。

以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v, T则是尚未确定到源点v最短路径的顶点集合。

然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。

直到T集合为空为止。

三、算法描述（步骤）1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径：①记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。

②设一个用来记录从源点到其它顶点的路径数组path[]，path中存放路径上第i个顶点的前驱顶点。

2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。

3、调整T中各顶点到源点v的最短路径。

因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。

调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。

4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

四、算法实现（数据结构）1、算法实现输入：一个大于1的整数n.输出：●一个随机生成的有向图G=（V，E），对于每一条边，有一个非负数字c(u，v)与之相关。

●对于每个顶点v∈V,得到从v0到v的最短路径的长度。