)Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。
/* Dijkstra.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex【3】;
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex【3】;
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex【3】;
char path【3】;
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i {
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex【0】='v';
poin->vertex【1】='0'+i+1;
poin->vertex【2】='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j {
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex【0】='v';
lin->vertex【1】='0'+temp;
lin->vertex【2】='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:\n");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i {
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex【0】='v';
p->vertex【1】='0'+i+1;
p->vertex【2】='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex【0】='v';
p->vertex【1】='0'+i+1;
p->vertex【2】='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex【1】==now->vertex【1】)
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex【1】;
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex【1】==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path【0】='v';
searc->path【1】=now->vertex【1】;
searc->path【2】='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost {
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex【1】-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex【1】-'0')!=start&&p!=NULL)
{
while(temp->vertex【1】!=p->path【1】&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("\n%s",p->vertex);
return OK;
}
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。
在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 初始化
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijstra算法主体
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d[u] + w(u,v) // 拓展边(u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。
现在我们可以通过迭代来回溯出s到t的最短路径
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]
现在序列S就是从s到t的最短路径的.
我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。相关问题和算法
在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。
OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。
与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。
如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。
