Dijkstra算法原理和证明

[Jaly]

算法：

设G是带权图，图中的顶点多于一个，且所有的权都为正数。本算法确定从顶点S到G中其他各个顶点的距离和最短通路。在本算法中P表示带永久标记的顶点的
集合。顶点A的前驱是P中的一个顶点，用来标记A。顶点U和V之间的边上的权用W（U， V）表示，如果U和V之间没有边，则记作W(U,V)=∞.

步骤1 （对S做标记）

（a）将S标记为0，并使S没有前驱

（b）令P={S}

步骤2 （对其他顶点作标记）

将每个不在P中的顶点V标记为W(S,V)(可能是暂时的），并使V的前驱为S（可能是暂时的）

步骤3 （扩大P，修改标记）

Repeat

步骤3.1 （是另一个标记永久化）

把不在P中且带有最小标记的顶点U加入到P中去（如果这样的顶点有多个则任选其中一个）

步骤3.2 （修改临时标记）

对每个不在P中并且和U相邻的顶点X，把X的标记替换为下列这两者中的较小者：i)X的旧标记,ii)U上的标记与
W（U，X）之和。如果X的标记改变了，则使U成为X的新前驱（可能是暂时的）

Until P包含G中的每一个顶点

步骤4 （求出距离和最短通路）

顶点Y上的标记是从S到Y的距离。如果Y上的标记是∞，那么从S到Y就没有通路，从而

没有最短通路；否则，按照下列序列的逆序使用顶点就构成从S到Y的一条最短通路：

Y，Y的前驱，Y的前驱的前驱，。。。。，直至S





证明：Dijkstra算法给出了从S到G的各个顶点的最短通路长度。



我们假设Ｇ中的每个顶点Ｖ都被赋予了一个标记L(V),它要么是一个数，要么是∞。假设P是G的顶点的集合，P包含S，满足：

1）如果V属于P，则L（V）是从S到V的最短通路的长度，并且存在这样的从S到V的最短通路：通路上的顶点都在P中

2）如果V不属于P，则L(V)是从S到V的满足下面限制的最短通路的长度：V是通路中唯一一个不属于P的顶点。



我们可以用归纳法证明Dijkstra算法中的P符合上述定义的集合：

1）当P中元素个数为1时，P对应算法中的第一步，P={S},显然满足。

2）假设P中元素个数为K时，P满足上述定义，下面看算法的的第三步，

先找出不在P中且带有最小标记的顶点U，标记为L(U), 可以证明从S到U的最短通路中除U外不包含不属于P的元素。

因为若存在除U外其他顶点，则最短通路为SP1P2...PnQ1Q2...QnU(P1,P2..Pn属于P,Q1,Q2,...Qn不属于P),则
由性质2）最短通路长度为L(Q1)+PATH(Q1,U)>L(U)

从而大于SP1P2..PnU的通路长度L(U)，不是最短通路，所以从S到U的最短通路中除U外不包含不属于P的元素，从而从S到U的最短通路长度由
L(U)给出.

现把U加入P中构成P' ,显然P'满足性质1)。

取V不属于P',显然V也不属于P,那么从S到V的最短通路且满足除V外所有顶点都在P'中的通路有两种可能，i）包含U，ii）不包含U。

对i）SP1P2...PnUV=L(U)+W(U,V)

ii)SP1P2..PnV=L(V)

显然二者中的最小给出了从S到V的最短通路且满足除V外所有顶点都在P'中的长度。

从而算法第三步给出的P'含K+1个元素且满足1),2)。

又归纳，命题得证！


Java Code:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Vector;


/**
* A Graph is a collection of Vertices and Edges
*
* @author yovn
*
*/
public class Graph {



private Map verticesMap;

public static class Vertex
{
private String name;
private Vector edges;

//implementation details
private Vertex previous;
private int total;

public Vertex(String name)
{
this.name=name;
edges=new Vector();
}

public void addEdge(Vertex toV, int w)
{
if(this.equals(toV))throw new RuntimeException("Same
Vertex");
edges.add(new Edge(this,toV,w) );
}
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 :
name.hashCode());
return result;
}
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Vertex other = (Vertex) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}


}

/**
* One Edge have two vertices and its weight
* @author yovn
*
*/
public static class Edge
{
Vertex v1;
Vertex v2;
int weight;

public Edge(Vertex v1,Vertex v2,int w)
{

this.v1=v1;
this.v2=v2;
weight=w;
}

/**
* Get the edge 's vertex but not the specified one
* @param one
* @return
*/
public Vertex getOtherVertex(Vertex one)
{
return v1.equals(one)?v2:(v2.equals(one)?v1:null);
}

public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((v1 == null) ? 0 :
v1.hashCode());
result = prime * result + ((v2 == null) ? 0 :
v2.hashCode());
return result;
}

public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Edge other = (Edge) obj;
if (v1 == null) {
if (other.v1 != null)
return false;
} else if (!v1.equals(other.v1))
return false;
if (v2 == null) {
if (other.v2 != null)
return false;
} else if (!v2.equals(other.v2))
return false;
return true;
}




}
/**
*
*/
public Graph() {
verticesMap=new HashMap();


}


public void addVertex(Vertex v)
{
verticesMap.put(v.name, v);

}

public void addVertex(String s)
{
Vertex v=new Vertex(s);
verticesMap.put(s, v);

}

/**
* Find the shortest path between the two specified Vertices
* @param from
* @param to
*/
public void printShortPath(Vertex from,Vertex to)
{
Set todo=new HashSet(verticesMap.values());
Set done=new HashSet();

//start from 'from' vertex and mark its 'total' to zero
Vertex cur=from;
cur.previous=null;
cur.total=0;
do
{

todo.remove(cur);
done.add(cur);


System.out.println("mark :"+cur.name);
Iterator it=cur.edges.iterator();

//base on the start vertex, update its associated
vertices' mark value(total)
while(it.hasNext())
{
Edge ed=(Edge)it.next();
Vertex v=ed.getOtherVertex(cur);

//don't back forward
if(done.contains(v))continue;

if(v.previous==null||v.total>cur.total+ed.weight)
{
//update 'v'
v.previous=cur;
v.total=cur.total+ed.weight;
}


}

//then, find next minimum marked value
it=todo.iterator();
Vertex min=null;
while(it.hasNext())
{
Vertex v=(Vertex)it.next();
if(v.previous!=null&&(min==null||v.total<min.total))
{
min=v;

}



}
cur=min;

}
while(!todo.isEmpty());

//all done, then print the result

System.out.println("total="+to.total);

StringBuffer buffer=new StringBuffer();

while(to!=null)
{
buffer.append(to.name);
if(to.previous!=null)
{
buffer.append(">-");
}
to=to.previous;


}
System.out.println(buffer.reverse());

}

public Vertex getVertex(String s)
{
return (Vertex)verticesMap.get(s);
}
/**
* A Graph example
*
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
* @param args
* @throws Exception
*/
public static void main(String[] args)throws Exception
{
Graph g=new Graph();
String[]
vs={"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"};

//make vertex
for(int i=0;i<vs.length;i++)
{
g.addVertex(vs[i]);
}

//init edges and their weight
g.getVertex("S").addEdge(g.getVertex("B"), 8);
g.getVertex("S").addEdge(g.getVertex("E"), 3);

g.getVertex("E").addEdge(g.getVertex("S"), 3);
g.getVertex("E").addEdge(g.getVertex("F"), 2);
g.getVertex("E").addEdge(g.getVertex("J"), 6);

g.getVertex("J").addEdge(g.getVertex("E"), 6);
g.getVertex("J").addEdge(g.getVertex("K"), 5);


g.getVertex("B").addEdge(g.getVertex("S"), 8);
g.getVertex("B").addEdge(g.getVertex("F"), 3);
g.getVertex("B").addEdge(g.getVertex("A"), 4);

g.getVertex("A").addEdge(g.getVertex("B"), 4);
g.getVertex("A").addEdge(g.getVertex("G"), 1);
g.getVertex("A").addEdge(g.getVertex("C"), 2);

g.getVertex("C").addEdge(g.getVertex("A"), 2);
g.getVertex("C").addEdge(g.getVertex("H"), 2);
g.getVertex("C").addEdge(g.getVertex("D"), 7);

g.getVertex("D").addEdge(g.getVertex("C"), 7);
g.getVertex("D").addEdge(g.getVertex("I"), 5);






g.getVertex("F").addEdge(g.getVertex("E"), 2);
g.getVertex("F").addEdge(g.getVertex("B"), 3);
g.getVertex("F").addEdge(g.getVertex("G"), 6);
g.getVertex("F").addEdge(g.getVertex("K"), 1);

g.getVertex("G").addEdge(g.getVertex("F"), 6);
g.getVertex("G").addEdge(g.getVertex("A"), 1);
g.getVertex("G").addEdge(g.getVertex("H"), 7);
g.getVertex("G").addEdge(g.getVertex("L"), 1);

g.getVertex("H").addEdge(g.getVertex("G"), 7);
g.getVertex("H").addEdge(g.getVertex("C"), 2);
g.getVertex("H").addEdge(g.getVertex("I"), 2);
g.getVertex("H").addEdge(g.getVertex("M"), 1);

g.getVertex("I").addEdge(g.getVertex("H"), 2);
g.getVertex("I").addEdge(g.getVertex("D"), 5);
g.getVertex("I").addEdge(g.getVertex("T"), 2);






g.getVertex("K").addEdge(g.getVertex("J"), 5);
g.getVertex("K").addEdge(g.getVertex("F"), 1);
g.getVertex("K").addEdge(g.getVertex("L"), 1);

g.getVertex("L").addEdge(g.getVertex("K"), 1);
g.getVertex("L").addEdge(g.getVertex("G"), 1);
g.getVertex("L").addEdge(g.getVertex("M"), 3);

g.getVertex("M").addEdge(g.getVertex("L"), 3);
g.getVertex("M").addEdge(g.getVertex("H"), 1);
g.getVertex("M").addEdge(g.getVertex("T"), 3);

g.getVertex("T").addEdge(g.getVertex("M"), 3);
g.getVertex("T").addEdge(g.getVertex("I"), 2);


//will find the shortest path between 'S' to 'T'
g.printShortPath(g.getVertex("S"), g.getVertex("T"));
}
}