Dijkstra

From :http://www.cs.bgu.ac.il/~vassilii/forth-opt/Dijkstra_8java-source.html
Dijkstra.java Go to the documentation of this file.
00001 // $Header: /home/vassilii/BGU/courses/fp042/forth-opt/RCS/Dijkstra.java,v 2.0 2004/09/05 00002
00003 import java.util.*;
00004
00005 public class Dijkstra implements PathFinder {
00006
00007 public Iterator findShortestPath(Vertex source, Vertex destination) {
00008 Map s = new HashMap();
00009 PriorityQueueSet q = new PriorityQueueSet();
00010 q.enqueue(source, 0, null);
00011
00012 while (!q.isEmpty()) {
00013 //u <- extract-min(q)
00014 Element u = q.dequeue();
00015 if (u.vertex.equals(destination)) return extractPath(u, s);
00016 // s <- s U {u}
00017 s.put(u.vertex, u);
00018 for (Iterator iter = u.vertex.outgoingEdges(destination); iter.hasNext();) {
00019 Edge e = (Edge) iter.next();
00020 Vertex v = e.destination();
00021 if (!s.containsKey(v))
00022 q.enqueue(v, u.distance + e.weight(), e);
00023 }
00024 }
00025 return new ArrayList().iterator(); // empty for no path found
00026 }
00027
00028 static private Iterator extractPath(Element elm, Map s) {
00029 LinkedList l = new LinkedList();
00030
00031 for (Edge e = elm.previous; e != null; e = ((Element)s.get(e.source())).previous)
00032 l.addFirst(e);
00033 return l.iterator();
00034 }
00035
00036 static class PriorityQueueSet {
00037 SortedSet q = new TreeSet();
00038 Map lookUp = new HashMap();
00039
00044 public void enqueue(Vertex v, int d, Edge e) {
00045 if (!lookUp.containsKey(v)) {
00046 Element elm = new Element(v, d, e);
00047 lookUp.put(v, elm);
00048 q.add(elm);
00049 } else {
00050 Element elm = (Element)lookUp.get(v);
00051 if (elm.distance > d) {
00052 q.remove(elm);
00053 elm.distance = d;
00054 elm.previous = e;
00055 q.add(elm);
00056 }
00057 }
00058 }
00059
00064 public Element dequeue() {
00065 if (q.isEmpty()) return null;
00066 Element elm = (Element)q.first();
00067 q.remove(elm);
00068 lookUp.remove(elm.vertex);
00069 return elm;
00070 }
00071
00072 public boolean isEmpty() { return q.isEmpty(); }
00073
00074 public String toString() { return q.toString(); }
00075 }
00076
00077 static class Element implements Comparable {
00078 final Vertex vertex;
00079 int distance;
00080 Edge previous;
00081
00082 public Element(Vertex v, int d, Edge e) {
00083 this.vertex = v;
00084 this.distance = d;
00085 this.previous = e;
00086 }
00087
00088 public int compareTo(Object o) {
00089 Element k = (Element)o;
00090 if (k.distance == this.distance)
00091 return this.vertex.compareTo(k.vertex);
00092 else
00093 return this.distance - k.distance;
00094 }
00095
00096 public boolean equals(Object o) {
00097 Element k = (Element)o;
00098 return this.distance == k.distance && this.vertex.equals(k.vertex);
00099 }
00100
00101 public String toString() {
00102 return "["+vertex+","+distance+","+previous+"]";
00103 }
00104 }
00105 }
Generated on Tue Sep 21 21:39:11 2004 for FORTH stack optimization by 1.3.8

Graph

带权路径长度最短-最优二叉树

回路 简单路径 简单回路 连通 连通图 连通分量-图中最大的连通子图 无向图

强连通图 强连通分量 有向图

有根的图 图的根 边带权的图为网络 无向网络 有向网络

图的存储

1.邻接矩阵

n个顶点的图 A[i,j]=1 i->j 有边； 0 i->j 无边

n个顶点的网络 wij,0(i=j),无穷

邻接矩阵只表示顶点之间的关系，使用顺序表存储图中顶点数值(顶点表)

2.邻接表

顶点表（n个元素）的顺序表（每个元素至少应包含一个指针字段first，用来指向每个链表的第一个结点）+

图的存储算法：

//顶点表中元素类型

struct node{

int degree;//顶点的度

arcnode *first ;//链表的首指针

}

struct arcnode{

int vertext; //相邻的顶点字号

int weight ;//边的权值

arcnode * next ;//指向链表的下一个结点

}

node adjlist[n0+1];//顶点表

int n ;//图的顶点数

void setgraph(){

int i,j,w;

//init

cin>>n;

for(int i=1;i<=n;i++){

adjlist[i].degree = 0;

adjlist[i].first = NULL;

}

//读入第一条边

cin>>i>>j>>w;

while((i>=1)&&(i<=n)){

//存入邻接表

p=adjlist[i].first;

while((p!=NULL)&&(p->vertext!=j)){

p=p->next;

}

if(p==NULL){

p = new arcnode;

p->vertext=j;

p->weight = w;

p->next=adjlist[i].first;

adjlist[i].first = p ;

++(adjlist[j].degree);

}

cin>>i>>j>>w;//读入下一条边

}

}

遍历：

1.深度遍历 2.广度遍历

定义一个顶点是否被访问过的标记数组 mark[i]

深度遍历的特点"后进先出" -使用栈

广度遍历的特点"先进先出"-使用队列

深度遍历算法：

void deeptrarverse(int x){

int mark[n0+1] , k;

int s[n0+1],t;

arcnode *p;

for(k=1;k<=n;k++) mark[k]=0;

cout<

mark[x]=1;

t=1;s[t]=x;//将深度经过的结点压入栈中

do{

k=s[t];//始终对栈顶元素进行操作

p=adjlist[k].first;//临时的首指针

while(p&&mark[p->vertex]){

p=p->next;//存在和栈顶元素的链接，但已被访问过，向下遍历查找无访问过的结点

}

if(p==NULL){

t--;//邻接的结点全部访问过则弹出栈顶元素

}else{

x=p->vertex;//未访问过则进行访问并把它置于栈顶重复上面操作

cout<

mark[x]=1;

s[++t]=x;

}

}while(t)//栈空结束

}

广度遍历：

void widetraverse(int x){

int q[n0+1],f=1,r=2;

cout<

q[1]=x;

arcnode * p ;

for( int k=0;k

mark[x]=1;

do{

k=q[f++];

p=adjlist[k].first;

while(p){//如果x的邻接结点未访问，一次访问全部的邻接结点放入队尾

if(mark[p->vertex]==0){

cout<vertex<<" ";

mark[p->vertex]=1;

q[r++]=p->vertex;

}

p=p->next;

}

}while(f!=r)

}

图的生成树

深度优先生成树 广度优先生成树

最小生成树 最短路径

在无回路的有向网络中，假设只有一个入度为0的顶点（源点）和一个出度为0的点（汇点） ，之间最长的路径为关键路径

单源最短路径问题：

Dijkstra 基本思想

算法基本思想 　设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。①初始化 　初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。②重复以下工作，按路径长度递增次序产生各顶点最短路径 　在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。 　当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 注意： 　①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。 　②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集 　根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是： 　源点，红点1，红点2，…，红点n，蓝点k 距离为：源点到红点n最短距离+<红点n,蓝点k>边长 　为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。 　若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]=SD(k)。 　初始时，每个蓝点v的D[c]值应为权w，且从s到v的路径上没有中间点，因为该路径仅含一条边。 注意： 　在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
（4）k扩充红点集s后，蓝点集估计距离的修改 　将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。 　对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=。且D[j]减小的新路径P只可能是由于路径和边组成。 　所以，当length(P)=D[k]+w小于D[j]时，应该用P的长度来修改D[j]的值。
（5）Dijkstra算法
Dijkstra(G，D，s){ //用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s}；D[s]=0； //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]； //设置i初始的估计距离为w
//以下是扩充红点集
for(i=0;i
/最多扩充n-1个蓝点到红点集
D[k]=min{D[i]：all i V-S}；
//在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞) return；
//蓝点集中所有蓝点的估计距离均为∞时，
//表示这些顶点的最短路径不存在。
S=S∪{k}； //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时，用新路径的长度修改D[j]，
//使j离s更近。
D[j]=D[k]+G[k][j]； }
}

栈和队列

栈先进后出 队列 先进先出

1.顺序栈

struct stack{

datatype s[n0+1];

int t ;

}

void push(stack & L, datatype x){

if(L.t==n0){

cout<<"栈满";

else

L.s[++L.t]=x;

}

}

void pop(stack & L){

if(L.t==0)

cout<<"empty";

else

L.t--;

}

2.链接栈

struct node{

datatype data ;

node * next ;

}//t是栈顶指针

void push(node * &t,datatype x){

node * p;

p = new node ;

p->next=t;

p->data=x;

t=p;

}

void pop (node * & t){

node * p;

if(t==NULL)

cout<<"栈空";

else {

p=t;

t=t->next;

delete p;

}

}

表达式求值：

数字串转换为整数值

v=0;

do{

v = 10 * v + c-'0';

cin>>c;

}while((c>='0')&&(c<='9'))

顺序队列

队列中最多容纳n0个元素 插入新元素之前，若出现(r+1)mod(n0+1)等于f则说明队列已满，若在删除操作之前，若出现f等于r，则说明队列已空，不能删除。

队列中元素个数为n=(rear-front+n0+1)mod(n0+1)

插入：

struct queue{

datatype q[n0+1];

int f,r;

}

void enq(queue & qu,datatype x){

if((qu.r+1)%(n0+1)==qu.f)){

cout<<"已满";

}

else{

qu.q[qu.r]=x;

qu.r=(qu.r+1)%(n0+1);

}

}

删除 qu.f=(qu.f+1)%(n0+1)

线性表

顺序表

#define n0 100

#define datatype int

struct sqlist{

datatype[n0+1];

int n;

}

插入的平均移动次数n/2，删除的平均移动次数n-1/2 执行时间O(n)

约瑟夫问题：每次有一位出列后，后面的元素都向左移动一位，列长减一

下次出列的位置=[上次出列的位置+m值（循环次数）-1]mod 当前列长i

线性链表：链接方法存储的线性表称为线性链表，简称链表

单向链表中表头结点简化插入删除操作，不修改表头指针。

循环单向链表：最后一个结点的指针字段存入第一个结点或表头结点的地址，可以立即访问到链表的最后一个结点。便于链表的首位相连的合并操作。

两种描述链表的方法：1.利用数组类型构成静态链表 2.利用指针类型构成动态链表

#define datatype int

struct node{

datatype data;

node * next ;

}

stuct linklist{

node *head ;//表头指针

int n ; //线性表长度

}

定位：第i个结点，若存在则返回该结点的地址 node * loc(linklist L,int i);，否则返回表头结点

p=L.head;j=0;

if((i>=1)&&(i<=L.n))

while(j

p=p->next;

j++;

}

return p;

插入：void( linklist & L,int i,datatype x){

node * p, *q;

p=loc(L,i);

q=new node;

q->data = x;

q->next=p->next;

p->next=q;

L.n++;

}

双向链表

插入新结点

q->prior = p ;

q->next = p->next;

p->next = q ;

q->next->prior=q;

删除结点

p->prior->next=p->next;

p->next->prior=p->prior;

静态链表

#define n0 100

#define datatype char

struct element{

datatype data;

int next ;//指针字段

}

element S[n0+1];//链表存储空间

int head ;//表头指针

多项式相加问题