我想要得到一个图的最短路径,两点间权值相同的最短路径可能不止一条,用哪种算法可以得到全部的最短路径呢????
解决方案 »
- 递归的实现过程咋写?
- java调用DLL,需要怎么走?
- 有谁能帮帮我把这个转成dowhile的形式么
- javax.xml.*;在哪里
- 各位大虾,有一个java,mvc程序,帮忙调试,100分献上,外加50元,很急!!
- 超出合法范围的值赋给一 变量,该变量的值如何?有请
- 为什么jcreator 可以运行但是 明两行却不可以?????郁闷中
- 怎么把java写的程序能弄成一个exe为后缀的可执行文件?
- 到底是太简单还是太难啊,怎么问了三次都没人答呢?
- 我用Javamail给对方发送邮件,如何判断对方是否已经收到邮件?
- 高分求一SWT编译不通过
- 泛型类申明对象, 和课本一样的代码, 课本的运行结果是“一只小狗 一只小花猫” ,可实际上根本不能运行,是哪里出错了呢。
// 最短路径的ijkstra算法:
public void Dijkstra(int v0) {
int s[] = new int[MaxVertices];
int v, i, j, w;
/* 初始化s、dist和path */
for (v = 0; v < CurrentVertices; v++) {
s[v] = 0; /* 0表示还未求出最短路径 */
/* 一开始假定取直达路径最短 */
dist[v] = Edge[v0][v];
/* 直达情况下的最后经由点就是出发点 */
if(dist[v] < MaxValue)
path[v] = v0;
else
path[v] = -1; /* 无直达路径 */
}
/* 初始时源点v0∈S集,表示v0到v0的最短路径已经找到 */
dist[v0] = 0;
s[v0] = 1;
// 下来假设经由一个点中转到达其余各点,会近些,验证之.
// 再假设经由两个点中转,会更近些,验证之,.....
// 直到穷举完所有可能的中转点.
double min;
for (i = 1; i < CurrentVertices - 1; i++) {
// 挑一个距离最近经由点,下标装入v
min = MaxValue;
for (w = 0; w < CurrentVertices; w++)
/* 顶点w不属于S集且离v0更近 */
if(s[w] == 0 && dist[w] < min) {
v = w; /* 经由顶点w中转则距离更短 */
min = dist[w];
}
s[v] = 1; /*
* 顶点v并入S,
* 由v0到达v顶点的最短路径为min
*/
/*
* 假定由v0到v,再由v直达其余各点,
* 更新当前最后一个经由点及距离
*/
for (j = 0; j < CurrentVertices - 1; j++)
if(s[j] == 0 && (min + Edge[v][j] < dist[j])) {
/*
* 如果多经由一个v点到达j点的
* 最短路径反而要短,就更新.
*/
dist[j] = min + Edge[v][j];
path[j] = v; /* 经由点的序号 */
}/* if */
}/* 循环for i */
}/* Dijkstra算法结束 */
需要看收集蛮多资料,然后自己慢慢消化掉吧.