《算法设计与分析》--单源最短路径随笔

1、概述:其实就是给定我们一个带权的有向图G=(V,E),其中每条边的权是非负实数，并且给定V中的一个顶点源，其实就是计算顶点源到其他顶点的最短距离。

2、算法的思想:狄杰斯特拉算法时解决该问题的一个比较好的贪心算法。我们可以设置一个顶点的集合S并且不断的做出贪心选择来扩充这个集合。最开始的时候集合S中只是仅仅含有源，设置u是G的某一个顶点，把从源到u且中间只是经过S中顶点的路成为从源到u的特殊路径，使用dist数组记录当前的每个顶点所对应的的最短特殊路径长度。

事实上每次Dijkstra算法都是每次从V-S中取出最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist进行必要的修改。最后D包含了V中所有顶点，dist就记录了从源到所有其他顶点的最短路径长度。

下面贴出部分代码段:

public static void dijkstra(int[] v,float[][] a,float[] dist,int[] prev){
//单元最短路径的Dijkstra算法
int n dist.length-1;
if(v<1 || v>n)return;
boolean[] s = new boolean[n+1];
//初始化
for(int i =1;i<=n;i++){
dist[i] = a[v][i];
s[i] = false;
if(dist[i] == Float.MAX_VALUE)prev[i]=0;
else prev[i] = v;
}
dist[v] = 0;s[v] = true;
for(int i =1;i<n;i++){
float temp = Float.MAX_VALUE;
int  u = v;
for(int j = 1;j<=n;j++)
if((!s[j] && (dist[j]<temp)){
u = j;
temp = dist[j];
}
s[u] = true;

for(int j = 1;j<=n;j++)
if((!s[j]) && (a[u][j]<Float.MAX_VALUE)){
float newdist = dist[u]+a[u][j];
if(newdist<dist[j]){
//dist[j]减少
dist[j] = newdist;
prev[j] = u;
}
}
}
}