Ⅰ 求A到B之间的最短路径，怎么获取
问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有着名的启发式搜索算法A*，不过A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。
(1) 迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是next点)递增次序产生最短路径。先把V分成两组：
S：已求出最短路径的顶点的集合
V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦）。
(2) 求最短路径步骤
初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值， 若存在<V0,Vi>，为<V0,Vi>弧上的权值（和SPFA初始化方式不同），若不存在<V0,Vi>，为Inf。
从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要)，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值（上面两个并列for循环，使用最小点更新）。
重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。
Ⅱ 利用Dijkstra算法求有向网图的最短路径
v1到v2：10为最短路径；
v1到v3：7为最短路径；
v1到v4:8为最短路径；
v1到v5：v1->
v2
->
v5
=10+6=
16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15;
15为最短路径；
v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；
v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；
v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径
Ⅲ 求解：图论中常见的最短路径算法有几种都是什么
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
Ⅳ 设计一个算法，计算出给定二叉树中任意2 个结点之间的最短路径。
对于树中的每一个节点，维护一个dis[i]，代表i节点到根节点路径长度。
写一个Lca(x,y)函数，用来返回x节点和y节点的最近公共祖先是哪一个节点。
树中最近公共祖先很很多种求法：
在信息学竞赛中一般使用的是倍增法，或者动态树。
如果你只是写一个普通的程序那么你可以朴素的取查找。当然程序会相对应的慢一点。
算法流程如下：
k=Lca(x,y);
dist=dis[x]+dis[y]-2*dis[k];//画个图就理解拉。
Ⅳ 用弗洛伊德算法求最短路径
是地信的题吧，先给你说v1怎么求，
先找出v1能去的最近的点，为V2，
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2，在其余的点中找距V1最近的，按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离
Ⅵ floyd算法求最短路径
Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单
缺点：时间复杂度比较高，不适合计算大量数据。
时间复杂度:O(n^3)；空间复杂度:O(n^2)；
任意节点i到j的最短路径两种可能：
直接从i到j；
从i经过若干个节点k到j。
map（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查map（i，k）+map（k，j）小于map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。
步骤：
第1步：初始化map矩阵。
矩阵中map[i][j]的距离为顶点i到顶点j的权值；
如果i和j不相邻，则map[i][j]=∞。
如果i==j，则map[i][j]=0;
第2步：以顶点A(假设是第1个顶点)为中介点，若a[i][j] > a[i][1]+a[1][j]，则设置a[i][j]=a[i][1]+a[1][j]。
Ⅶ floyd算法求最短路径怎么用
Dijkstra算法
1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2.算法描述
1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
Ⅷ 求写最短路径算法。由A地到E地，途经B（B1，B2，B3）C（C1，C2，C3）地，基于矩阵乘法求最短路径。给出步骤
们把求A →E 的最短路分解为四个阶段A →B →C→D →E 来求解。每一个阶段可以用一个矩阵来表示，这个矩阵称为权矩阵。相邻阶段的路径可以用权矩阵的乘积来表示。但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大. 如果是求极大,改为取大运算,此时如果不同层节点间没有连接，则视它们的距离为0。
如下：
由A地到B地的距离可表示为：A[2 5 8]
由B地到C地的权矩阵可表示为
[3，6，5；7，10，8；4，9，6]
因此由A到C的权矩阵为[2，5，8][3，6，5；7，10，8；4，9，6]＝[5，8，7]
因此由A到D的权矩阵为[5，8，7)][7，5；3，4；5，2]＝[11 ，9]
由A→E的权矩阵为：[11 ，9][4，2)]=[15,11]
因此从家里到学校的最短距离为11百米，最近的路径为从A地出发经过B1地C1地D2地到达E地。
下面我们给出基于“矩阵乘法”求解最短路的算法:
第一阶段:计算出图中从起始点到终点最短路的长度.
step1 划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;
step2 依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 , …, N21) ; (若第i 层有m 个顶点;第i + 1 层有n
个顶点, 则从第i 层到第i + 1 层的权矩阵为m *n
阶) .
step3 按照我们定义的矩阵乘法计算出最短路的
数值.
第二阶段:寻找最短路所经过的中间点.
(利用第一阶段中step2 的数据) 计算出从第i 层到
终点的最短路, 对比与i21 层到终点的最短路, 从而确
定出第i 层上最短路所经过的顶点( i = 2 , …, N21) .
Ⅸ 数据结构中迪杰斯特拉算法求最短路径
dijkstra算法本身求的是一点到其他所有点的最短距离，而不是具体的路径，因此还需要一个额外的数组来记录推导最短距离的过程中经过的每一个结点，这样才能求出这个最短距离的具体路径。