2013年（118）
分类： C/C++
2013-10-18 15:41:42
原文地址：数据结构深入剖析（15）--最短路径 作者：mq24705
一、 最短路径
1. 问题提出
如果从有向图中某一顶点（称为源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
2. 问题解法
单源最短路径问题：Dijkstra算法
所有顶点之间的最短路径：Floyd算法
3. 问题分析
问题的提法：给定一个带权有向图D与源点v，求从v到D中其他顶点的最短路径。
解决思路：Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v 到其它各顶点的最短路径全部求出为止。
4. 解决步骤描述
设置辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点v0 到终点vi 的最短路径的长度。
初始状态：
若从源点v0 到顶点vi 有边：dist[i]为该边上的权值；
若从源点v0 到顶点vi 无边：dist[i]为无穷
① 初始化：S←{ v0 };
dist[j] ←Edge[0][j], j = 1, 2, …, n-1;
② 找出最短路径所对应的点K：
dist[k] == min { dist[i] }, i 属于V- S ;
S←S U { k };
③ 对于每一个i 属于V- S 修改：
dist[i] ←min{ dist[i], dist[k] + Edge[k][i] }
④ 判断：若S = V,则算法结束，否则转②。
5. 算法实现
#include
#include
#define VNUM 5
#define MV 65535
int Dist[VNUM];
int Mark[VNUM];
int P[VNUM];
int Matrix[VNUM][VNUM] =
{
{0,10,MV,30,100},
{MV,0,50,MV,MV},
{MV,MV,0,MV,10},
{MV,MV,20,0,60},
{MV,MV,MV,MV,0}
};
void Dijkstra(int sv)
{
int i = 0;
int j = 0;
if((0 <= sv) && (sv < VNUM)){
for(i = 0;i < VNUM;i++){
Dist[i] = Matrix[sv][i];
P[i] = sv;//记录 i 顶点前面的顶点值为P[i]
Mark[i] = 0;
}
Mark[sv] = 1;
for(i = 0;i < VNUM;i++){
int min = MV;
int index = -1;
for(j = 0;j < VNUM;j++){
if(!Mark[j] && Dist[j] < min){
min = Dist[j];
index = j;
}
}
if(index > -1){
Mark[index] = 1;
}
for(j = 0; j < VNUM;j++){
if(!Mark[j] && (min + Matrix[index][j]) < Dist[j]){
Dist[j] = min + Matrix[index][j];
P[j] = index;
}
}
}
for(i = 0;i < VNUM;i++){
int p = i;
printf("%d -> %d: %d\n",sv,i,Dist[p]);
do{
printf("%d <-",p);
p = P[p];
}while(p != sv);
printf("%d\n",p);
}
}
}
int main(int argc, char *argv[])
{
Dijkstra(0);
return 0;
}
6. Floyd算法
（1） 基本思想
定义一个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
（2） A矩阵的意义
A(0) [i][j]是从顶点vi 到vj , 中间顶点是v0的最短路径的长度
A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度
A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度
（3） 算法实现
#include
#include
#define VNUM 5
#define MV 65535
int A[VNUM][VNUM];
int P[VNUM][VNUM];
int Matrix[VNUM][VNUM] =
{
{0,10,MV,30,100},
{MV,0,50,MV,MV},
{MV,MV,0,MV,10},
{MV,MV,20,0,60},
{MV,MV,MV,MV,0}
};
void Floyd()
{
int i = 0;
int j = 0;
int k = 0;
for(i = 0;i < VNUM;i++){
for(j = 0;j < VNUM;j++){
A[i][j] = Matrix[i][j];
P[i][j] = j;
}
}
for(i = 0;i < VNUM;i++){
for(j = 0;j < VNUM;j++){
for(k = 0; k < VNUM;k++){
if((A[j][i] + A[i][k]) < A[j][k]){
A[j][k] = A[j][i] + A[i][k];
P[j][k] = P[j][i];
}
}
}
}
for(i = 0;i < VNUM;i++){
for(j = 0;j < VNUM;j++){
int p = -1;
printf("%d -> %d: %d\n",i,j,A[i][j]);
printf("%d",i);
p = i;
do{
p = P[p][j];
printf(" -> %d",p);
}while(p != j);
printf("\n");
}
}
}
int main(int argc, char *argv[])
{
Floyd();
return 0;
}
