Question

c语言问题.

c语言问题.利用DJKSTRA算法和Floyd算法求最短路径~

Answer 1

Dijkstra算法可描述如下:
1初始化： S ← { v0 };
dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
// n为图中顶点个数
2求出最短路径的长度：
dist[k] ← min{ dist[i] }, i  V- S ;
S ← S U { k };
3修改：
dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },
对于每一个 i  V- S ;
4判断： 若S = V, 则算法结束，否则转2。
用于计算最短路径的图邻接矩阵类的定义

const int NumVertices = 6; //图中最大顶点个数
class Graph { //图的类定义
private:
int Edge[NumVertices][NumVertices]; //邻接矩阵
int dist[NumVertices]; //最短路径长度数组
int path[NumVertices]; //最短路径数组
int S[NumVertices]; //最短路径顶点集
public:
void ShortestPath ( const int, const int );
int choose ( const int );
};
计算从单个顶点到其它各个顶点的最短路径

void Graph::ShortestPath ( const int n, const int v ){
//Graph是一个具有n个顶点的带权有向图, 各边上
//的权值由Edge[i][j]给出。本算法建立起一个数
//组: dist[j], 0  j < n, 是当前求到的从顶点v到顶点
//j的最短路径长度, 同时用数组path[j], 0  j < n, 存
//放求到的最短路径。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist数组初始化
S[i] = 0;
if ( i != v && dist[i] < MAXINT ) path[i] = v;
else path[i] = -1; //path数组初始化
}

S[v] = 1; dist[v] = 0; //顶点v加入顶点集合
//选择当前不在集合S中具有最短路径的顶点u
for ( i = 0; i < n-1; i++ ) {
int min = MAXINT; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点u加入集合S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXINT &&
dist[u] + Edge[u][w] < dist[w] ) {
dist[w] = dist[u] + Edge[u][w];
path[w] = u;
}

Floyd算法的基本思想：
定义一个n阶方阵序列：
A(-1), A(0), …, A(n-1).
其中 A(-1) [i][j] = Edge[i][j]；
A(k) [i][j] = min { A(k-1)[i][j]，
A(k-1)[i][k] + A(k-1)[k][j] }, k = 0,1,…, n-1
A(0) [i][j]是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。

所有各对顶点之间的最短路径

void Graph::AllLengths ( const int n ) {
//Edge[n][n]是一个具有n个顶点的图的邻接矩阵。//a[i][j]是顶点 i 和 j 之间的最短路径长度。path[i][j]
//是相应路径上顶点 j 的前一顶点的顶点号, 在求
//最短路径时图的类定义中要修改path为
//path[NumVertices][NumVertices]。

for ( int i = 0; i < n; i++ ) //矩阵a与path初始化
for ( int j = 0; j < n; j++ ) {
a[i][j] = Edge[i][j];
if ( i <> j && a[i][j] < MAXINT )
path[i][j] = i; // i 到 j 有路径
else path[i][j] = 0; // i 到 j 无路径
}
for ( int k = 0; k < n; k++ ) //产生a(k)及path(k)
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
if ( a[i][k] + a[k][j] < a[i][j] ) {
a[i][j] = a[i][k] + a[k][j];
path[i][j] = path[k][j];
} //缩短路径长度, 绕过 k 到 j
}

Answer 2

奥赛经典这本书里面有很详细的..

Answer 3

数据结构 这本书上有原代码的 自己找本看吧...