数据结构之单流最短路径（迪杰斯特拉算法）-（九）
数据结构之单源最短路径（迪杰斯特拉算法）-（九）
最开始接触最短路径是在数据结构中图的那个章节中。运用到实际中就是我在大三参加的一次美赛中，解决中国的水资源问题。所谓单源最短路径，就是一个起点到图中其他节点的最短路径，这是一个贪心算法。
迪杰斯特拉算法原理（百科）：
按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，保证：
（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
（反证法可证）
求最短路径步骤
算法步骤如下：
G={V,E}
1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
java实现：
数据变化：
public class Graph
{
public static void main(String[] args)
{
// TODO Auto-generated method stub
int [][]distance=new int[7][7];
distance[0][1]=2;
distance[0][3]=1;
distance[1][3]=3;
distance[1][4]=10;
distance[2][0]=4;
distance[2][5]=5;
distance[3][2]=2;
distance[3][4]=2;
distance[3][5]=8;
distance[3][6]=4;
distance[4][6]=6;
distance[6][5]=1;
int []p=new int[distance.length];
int []d=getMinDistance(0, distance,p);
for(int i=1;i<d.length;i++)
{
System.out.println("the distance from 1 to "+(i+1)+":"+d[i]);
int temp=i;
System.out.print(temp+1+"<-");
while(p[temp]!=0)
{
System.out.print(p[temp]+1+"<-");
temp=p[temp];
}
System.out.println("1");
}
}
/*
* 迪杰斯特拉求单元最短路径
* 原理：
*/
/**
* 谈心策略，起点到w的最短距离=min{dv+c(v,w),dw},dv是已知的到节点v的最短距离
* @param start 要求的节点
* @param distance 邻接矩阵 表示相邻顶点的距离
* @param p 前置节点，到达该节点的前面节点
* @return
*/
public static int[] getMinDistance(int start,int [][]distance,int []p)
{
int []know=new int[distance.length];//起点到节点的距离是否已知
int []d=new int[distance.length];//起点到各个顶点的距离
/***********初始化距离*******************/
for(int i=0;i<d.length;i++)//初始情况下距离起点当然是无穷大
d[i]=Integer.MAX_VALUE;
d[start]=0;
/*************************************/
/****初始化know表示是否已知道最短距离********/
for(int i=0;i<know.length;i++)
know[i]=0;
/*************************************/
/****初始化最短节点的前置节点********/
for(int i=0;i<p.length;i++)
p[i]=0;
/*************************************/
while(true)
{
//所有的最短距离都已知道
if(isAllKnow(know))
break;
//找到d中最小的并且know=0的元素
int pos=0,i,min=Integer.MAX_VALUE;
for(i=0;i<d.length;i++)
{
if(min>d[i]&&know[i]==0)
{
min=d[i];
pos=i;
}
}
know[pos]=1;
/*************找到前置节点是pos的所有节点，更新距离***************/
for(i=0;i<distance.length;i++)
{
if(distance[pos][i]!=0)
{
if(d[i]>d[pos]+distance[pos][i])
{
d[i]=d[pos]+distance[pos][i];
p[i]=pos;
}
}
}
}
return d;
}
private static boolean isAllKnow(int []array)
{
for(int e:array)
{
if(e==0)
return false;
}
return true;
}
} 运行截图：