单源最短路径(两种方法)
单源最短路径
计科一班 李振华 2012040711
1、 问题描述
给定带权有向图G=(V ,E ),其中每条边的权是非负实数。另外,还给定V 中的一个顶点,称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
2、 问题分析
推导过程(最优子结构证明,最优值递归定义)
1、 贪心算法
对于图G ,如果所有Wij ≥0的情形下,目前公认的最好的方法是由Dijkstra 于1959年提出来的。
已知如下图所示的单行线交通网,每弧旁的数字表示通过这条单行线所需要的费用,现在某人要从v1出发,通过这个交通网到v8去,求使总费用最小的旅行路线。
Dijkstra 方法的基本思想是从vs 出发,逐步地向外探寻最短路。执行过程中,与每个点对应,记录下一个数(称为这个点的标号) ,它或者表示从vs 到该点的最短路的权(称为P 标号) 、或者是从vs 到该点的最短路的权的上界(称为T 标号) ,方法的每一步是去修改T 标号,并且把某一个具T 标号的改变为具 P标号的点,从而使G 中具P 标号的顶点数多一个,这样至多经过n-1(n为图G 的顶点数) 步,就可以求出从vs 到各点的最短路。
在叙述Dijkstra 方法的具体步骤之前,说明一下这个方法的基本思想。s=1。因为所有Wij ≥0,故有d(v1, v1)=0。这时,v1是具P 标号的点。现在考察从v1发出的三条弧,(v1, v2), (v1, v3)和(v1, v4)。
(1)如果某人从v1出发沿(v1, v2)到达v2,这时需要d(v1, v1)+w12=6单位的费用;
(2)如果他从v1出发沿(v1, v3)到达v3,这时需要d(v1, v1)+w13=3单位的费用;
(3)若沿(v1, v4)到达v4,这时需要d(v1, v1)+w14=1单位的费用。
因为min{ d(v1, v1)+w12,d(v1, v1)+w13,d(v1, v1)+w14}= d(v1, v1)+w14=1,可以断言,他从v1到v4所需要的最小费用必定是1单位,即从v1到v4的最短路是(v1, v4) ,d(v1, v4)=1。这是因为从v1到v4的任一条路P ,如果不是(v1, v4) ,则必是先从v1沿(v1, v2) 到达v2,或者沿(v1, v3) 到达v3。但如上所说,这时他已需要6单位或3单位的费用,不管他如何再从v2或从v3到达v4,所需要的总费用都不会比1小(因为所有wij ≥0) 。因而推知d(v1, v4)=1,这样就可以使v4变成具P 标号的点。
(4)现在考察从v1及v4指向其余点的弧,由上已知,从v1出发,分别沿(v1, v2) 、(v1, v3)到达v2, v3,需要的费用分别为6与3,而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12,d(v1, v1)+w13,d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言,从v1
到v3的最短路是(v1, v3) ,d(v1, v3)=3。这样又可以使点v3变成具P 标号的点,如此重复这个过程,可以求出从v1到任一点的最短路。
在下述的Dijstra 方法具体步骤中,用P ,T 分别表示某个点的P 标号、T 标号,si 表示第i 步时,具P 标号点的集合。为了在求出从vs 到各点的距离的同时,也求出从Vs 到各点的最短路,给每个点v 以一个λ值,算法终止时λ(v)=m,表示在Vs 到v 的最短路上,v 的前一个点是Vm ;如果λ(v)= ∞,表示图G 中不含从Vs 到v 的路;λ(Vs)=0。
Dijstra 方法的具体步骤:
{初始化}
i=0
S0={Vs},P(Vs)=0 λ(Vs)=0
对每一个vVs,令T(v)=+ ∞,λ(v)=+ ∞,
k=s
{开始}
①如果Si=V,算法终止,这时,每个v ∈Si ,d(Vs,v)=P(v);否则转入② ②考察每个使(Vk,vj)∈E 且vj Si的点vj 。
如果T(vj)>P(vk)+wkj,则把T(vj)修改为P(vk)+wkj,把λ(vj)修改为k 。 ③令
如果,则把的标号变为P 标号,令 ,k=ji,i=i+1,转①,否则终止,这时对每一个v ∈Si ,d(vs,v)=P(v),而对每一个。 在下图所给的有向图G 中,每一边都有一个非负边权。要求图G 的从源顶点
s 到目标顶点t 之间的最短路径。
2、分支限界法
算法从图G 的源顶点s 和空优先队列开始。结点s 被扩展后,它的儿子结点被依次插入堆中。此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i 到顶点j 有边可达,且从源出发,途经顶点i 再到顶点j 的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。
在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树。
在算法中,利用结点间的控制关系进行剪枝。从源顶点s 出发,2条不同
路径到达图G 的同一顶点。由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。
3、 计算求解过程、算法实现(源代码实现相关功能)
1、 贪心算法
#include
#include
using namespace std;
#define MAX 1000000 //充当" 无穷大"
#define LEN sizeof(struct V_sub_S)
#define N 5
#define NULL 0
int s; //输入的源点
int D[N]; //记录最短路径
int S[N]; //最短距离已确定的顶点集
const int G[N][N] = { {0, 10, MAX, 30, 100},
{MAX, 0, 50, MAX, MAX},
{MAX, MAX, 0, MAX, 10},
{MAX, MAX, 20, 0, 60},
{MAX, MAX, MAX, MAX, 0} };
typedef struct V_sub_S //V-S链表
{
int num;
struct V_sub_S *next;
};
struct V_sub_S *create()
{
struct V_sub_S *head, *p1, *p2;
int n = 0;
head = NULL;
p1 = (V_sub_S *)malloc(LEN);
p1->num = s;
head = p1;
for(int i = 0; i
{
if(i != s)
{
++ n;
if(n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (V_sub_S *)malloc(LEN);
p1->num = i;
p1->next = NULL;
}
}
free(p1);
return head;
}
struct V_sub_S *DelMin(V_sub_S *head, int i) //删除链表中值为 i 的结点
{
V_sub_S *p1, *p2;
p1 = head;
while(i != p1->num && p1->next !=NULL)
{
p2 = p1;
p1 = p1->next;
}
p2->next = p1->next;
return head;
}
void Dijkstra(V_sub_S *head, int s)
{
struct V_sub_S *p;
int min;
S[0] = s;
for(int i = 0; i
{
D[i] = G[s][i];
}
for(int i = 1; i
{
p = head->next;
min = p->num;
while(p->next != NULL)
{
if(D[p->num] > D[(p->next)->num])
min = (p->next)->num;
p = p->next;
}
S[i] = min;
head = DelMin(head, min);
p = head->next;
while(p != NULL)
{
if(D[p->num] > D[min] + G[min][p->num])
{
D[p->num] = D[min] + G[min][p->num];
}
p = p->next;
}
}
}
void Print(struct V_sub_S *head)
{
struct V_sub_S *p;
p = head->next;
while(p != NULL)
{
if(D[p->num] != MAX)
{
cout num num] next;
}
else
{
cout num
p = p->next;
}
}
}
int main()
{
struct V_sub_S *head;
cout
cin >> s;
head = create();
Dijkstra(head, s);
head = create();
Print(head);
system("pause"); return 0;
}
2、 分支限界法
#include
#include
using namespace std;
#define MAX 9999
#define N 60
int n,dist[N],a[N][N];
class HeapNode
{
public:
int i,length;
HeapNode() { }
HeapNode(int ii,int l)
{
i=ii;
length=l;
}
bool operator
{
return length
}
};
void shorest(int v)
{
priority_queue heap;
HeapNode enode(v,0);
for(int i=1; i
dist[v]=0;
while(1)
{
for(int j=1; j
if(a[enode.i][j]
enode.length+a[enode.i][j]
{
dist[j]=enode.length+a[enode.i][j];
HeapNode node(j,dist[j]);
heap.push(node);
}
if(heap.empty()) break;
else
{
enode=heap.top();
heap.pop();
}
}
}
int main ()
{
cin>>n;
for(int i=1; i
for(int j=1; j
{
cin>>a[i][j];
if(a[i][j]==-1) a[i][j]=MAX;
}
shorest(1);
for(int i=2; i
cout
return 0;
}
3、
运行结果(截图)
4、 计算复杂性分析(时间、空间)
求单源、无负权的最短路。时效性较好,时间复杂度为O (V*V+E), 可以用优先队列进行优化,优化后时间复杂度变为0(v*lgn)。
源点可达的话,O (V*lgV+E*lgV)=>O(E*lgV)。
当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为O (V^2) 。可以用优先队列进行优化,优化后时间复杂度变为0(v*lgn)。
5、 算法改进
Dijkstra 算法的运行时间要低,但它要求所有边的权值非负。Dijkstra 算法中设置了一个顶点集合S ,从源点s 到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点u ∈V-S ,并将u 加入S 中,对u 的所有出边进行松弛。由于总是在V-S 中选择“最近”的顶点插入集合S 中,可以说Dijkstra 算法使用了贪心策略。可以想象,在Dijkstra 算法的执行过程中,最短路径估计沿着以s 为根的最短路径树向下传播。由于不存在负权边,最短路径树中的边一旦确定就不再改变。可以使用最小堆构建的最小优先队列(同Prim 算法),存储集合V-S 中的顶点。Dijkstra 算法需要|V|次运行时间为O(lg V)的
heap_extract_min操作和|E|次运行时间为O(lg V)的heap_decrease_key操作,因此,总的运行时间为O((V+E) lg V) ,如果所有顶点都从源点可达的话,则为O(E lg V)。
成 绩 单