"Dijkstra 算法"计算出以下网络图中V2—V6 间的最短路径长度,求出最短路径,用矩阵表示求解过程.下面是图

高楼-暝色2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

滕朝ll 共回答了19个问题 | 采纳率84.2%: V2->V4->V3->V5->V6
最短路径为2+1+3+3=9; 1年前

求大神帮忙编程，c语言，求最短路问题，dijkstra的改进方法。 求大神帮忙编程，c语言，求最短路问题，dijkstra的改进方法。 伪代码 creat H[(n-1) c+1] ; //H是集合群， H[i】表示第i个集合 d(j)=∞ for all j∈N; //距离全设为 ∞ d(s)=0 pred(s)=0; //源点到自身的距离为0，标记前面的节点为源点 insert (s,H[0]); //源点插入到第0个集合 for k=0,(n-1)c //遍历所有的集合 for each i∈H[k] //遍历集合中所有的点 delete (i,H[k]); //将改的从集合中删去 for each (i,j)∈A(i) //遍历i点的每一条边 value=d(i)+cij; if d(j)>value then if d(j)=∞ then d(j)=value,pred(j)=i,insert(j,H[value]); else delete(j,H[d(j)]),d(j)=value,pred(j)=i,insert(j,H[value]); end; end; end; end; 方法： 算法把当前能到的有限个节点放到一个排序的结构中，他包含了（n-1）·c+1个集（n是顶点个个数，c是最大边的长度），我们把它们叫做桶，分别编号0，1······nc，第k个桶存放所有当前距离为k的点。距离为无穷大的点不需要存放，当这些点第一次出现有限距离时再放入桶中。用content（k）表示第k个桶。 （因为从源点到某一点i最多是把每一个顶点都走一遍，共经过n-1个点，所走的最短距离最多是d（i）=（n-1）·c 1、开始第0号桶，放源点，更新源点到其他节点的距离，把这些点存入相应的桶中。 d（i）=k，则content（k）=i 2、节点的选择，从0号桶开始，1，2···一个一个浏览桶，直到第一个非空的桶，里面存放点i，则d（i）是距离源点最近的点，标记i，将i从桶中删除。 3、以i为中间点更新距离， for each（i，j）∈A（i） do （ i所能到的点j） if d（j）>d(i)+cij then d(j)=d(i)+cij pred(j)=i 如果j的第一次出现有限距离，则放入桶中，如果从d（1)变成了d（2），且的d（2）4、在后续的迭代中，0到d（i）的桶都为空，可以不用考虑，从d（i）+1的点开始浏览，重复上述步骤，直到所有点都被删除。若想找到某一点的最短路，只需该点从桶中删去就可停止。 uualice1年前1: wwwhaocctv 共回答了17个问题 | 采纳率88.2%

/*
* File: shortest.c
* Description: 网络中两点最短路径 Dijkstra 算法
* Shortest Path Dijkstra Algorithm
* Created: 2001/11/25
* Author: Justin Hou [mailto:justin_hou@hotmail.com]
*/
#include
#define true 1
#define false 0
#define I 9999 /* 无穷大 */
#define N 20 /* 城市顶点的数目 */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存储当前最短路径长度 */
int v0 = 'A' - 65; /* 初始点是 A */
void main()
{
int final[N], i, v, w, min;
/* 初始化最短路径长度数据，所有数据都不是最终数据 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* 首先选v0到v0的距离一定最短，最终数据 */
final[v0] = true;
/* 寻找另外 N-1 个结点 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短长度无穷大 */
/* 寻找最短的边 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新边 */
for (w = 0; w < N; w++) { /* 更新 dist[] 数据 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* 显示到监视器 */
printf("%c->%c: %2dt", v0 + 65, i + 65, dist[i]);
}
}

1年前查看全部

运筹学最短路问题一般使用的方法是Dijkstra标号法,现在想请问能否用另外一种办法,即先画出最小支撑树,然后再进行计算 运筹学最短路问题 一般使用的方法是Dijkstra标号法,现在想请问能否用另外一种办法,即先画出最小支撑树,然后再进行计算,能否严格证明一下?急用, tawow1年前1: 如风似匕共回答了15个问题 | 采纳率100%

通过最小支撑树来求最短路的想法是不是认为求得了一个图的最小支撑树,则最小支撑树上任意两点间的链就是要求的最短路,这个没法保证的.以下引用一个别人的回答：在一棵最小生成树中,两点的距离在整个图中是最短的吗?...

1年前查看全部

Dijkstra 算法是什么?Dijkstra 在哪里用 忧郁mm1年前1: 狗狗媳妇儿共回答了21个问题 | 采纳率76.2%

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径,该算法按照最短路径长度递增的顺序产生所以最短路径.
对于图G=（V,E）,将图中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（开始为{v0}）.
第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）.
算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中,直到所有顶点都被加入到第一组顶点集S为止.
【算法思想】
g为用邻接矩阵表示的带权图.
（1）S

1年前查看全部

图论有哪些算法?除了floyd Dijkstra之外,具体点 hzlai20051年前1: mcuos 共回答了9个问题 | 采纳率88.9%

A.Prim算法、Kruskal算法、Floyed算法、Dijkstra 算法&amp和遗传算法等

1年前查看全部

三道有关高等数学算法的题,树和dijkstra, 三道有关高等数学算法的题,树和dijkstra, 都在上图里了,答案做成图答出来最好, 小蛇snake1年前0: 共回答了个问题 | 采纳率

查看全部

"Dijkstra 算法"计算出以下网络图中V2—V6 间的最短路径长度,求出最短路径,用矩阵表示求解过程.下面是图

共1条回复

相关推荐

大家在问