Dijkstra算法探索及优化

（前几天并多少时间，现在补充一下！）下面是原始的dijkstra算法：

public static void dijkstra(int v,float[][] a, flaot[] dist,int[] prev)
{
int n=dist.length-1;
if(v<1||v>n)return;
boolean[] s = new boolean[n+1];
//此处的循环是初始化
 for(int i=1; i<=n; i++)
{
dis[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;
//shortestPath（此处取该循环为shortestPath）
for(int j=1; j<n; j++)
{
if((!s[j])&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
}
s[u]=true;
//updateDist（取名为updateDist）
 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]=newdist;
prev[j]=u;
}
}
}
}
}

以前看过Dijkstra算法，但是一直没有深入的研究它！最近由于项目的需要，所以今天研究了一下！下面介绍一下这个算法几个重要的几点！

其实这个算法有两个比较重要的地方！在书上开始有一个循环，是对参数初始化。这个就没必要研究了！主要的是第二个循环里面的两个循环，第二个循环要进行n-1次（也就是循环节点个数减去源节点），这就是要取得其他节点到源节点的距离，一次循环就是取得一个节点到源节点的距离。那么在第二个循环里面的第一个循环（这里叫该循环为shortestPath）就是取得当前能够到达源节点最短的节点，并且该节点是未被访问过的节点。取得在未被访问的节点里面到源节点最短路径的节点u后，最一个循环就是修改和u节点相连的节点到源节点的距离（这里称该循环为updateDist），我这里称这一步为更新u的邻接节点到源节点的距离。再回到shortestPath循环，就有可能取到u的邻接节点。下面我谈谈对这个算法的改进。

我们知道在shortestPath循环中，在书上的源码都是要遍历图中所有的节点，这样我觉得存在极大的浪费，我们知道该步是取得在dis数组中到源节点最短的节点，并且该节点是未被访问过的，所以这里根本没必要遍历图中所有的节点，只需遍历dis数组中的节点，而且我们知道dist的新的距离都是通过updateDist循环得到的，所以我们完全可以将dist数组里的距离存储到一个集合中，我们可以自定义一个集合，当我们每次想该集合添加元素（也就是到源节点的距离）的时候自动对该集合中进行排序，进行递增排序，我们取该集合的第一个元素就是当前到源节点最短的节点，并且该节点是未被访问的，取出时并将该节点从该集合中移出。这样我们就省掉了shortestPath这个循环了，这样对算法的运行将有极大的提高！还有就是后面的updateDist循环，在书上的源码中也是对图中的所有节点进行遍历，其实也没必要，只需对u的领结节点遍历即使！这样有省掉了没必要的循环，这样的Dijkstra算法，我相信应该不会很慢！

注意的是这种优化也需要对你的图结构进行优化，具体的优化可以见本博客的《新颖的图存储结构【看来之后你会对图的结构有新的想法】》文章，里面有详细讲解一种图的存储结构！

下面贴出我改进的算法：

public class ShortestPathIterator_3 {

	private Graph graph;
	private boolean visited[];
	private int prev[];
	private int source;
	private int position;
	private float pathCost[];
	private int n;
	private Map<Integer,Float> visitable;
	//获得当前的源节点
	public int getSource()
	{
		return this.source;
	}
	public ShortestPathIterator_3(Graph graph,int source)
	{
		visited = new boolean[graph.getNode_Count()];
		this.visitable = new HashMap<Integer,Float>();
		prev = new int[graph.getNode_Count()];
		this.graph = graph;
		this.source = source;
		this.pathCost = new float[this.graph.getNode_Count()];
		for(int i=0; i<graph.getNode_Count(); i++)
		{
			this.pathCost[i]=Float.MAX_VALUE;
			this.visited[i]=false;
		}
		EdgeIterator edgeIterator = graph.getEdgeIterator(this.source);//获得所有和元节点相邻的节点集合
		int adjancentNode;
		while(edgeIterator.hasNext())
		{
		    adjancentNode = this.graph.getAdjancentNode(edgeIterator.next());	
		    this.pathCost[adjancentNode] = this.graph.getEdgePrestige(edgeIterator.next());
		    this.visitable.put(adjancentNode, this.graph.getEdgePrestige(edgeIterator.next()));
			this.prev[adjancentNode] = this.source;
		}
	    
	  	this.visited[this.source]=true;
	  	this.position=0;
	  	this.n=this.graph.getNode_Count()-1;
	  	
	}
	public int getNext()
	{
		Integer u = this.source;
		if(this.position<=this.n-1)
		{
			float temp = Float.MAX_VALUE;
	        Iterator<Integer> keyIterator = this.visitable.keySet().iterator();
	        int next; 
	        //取得未被访问并且，到源点最短的节点，并赋值给U，同时将和U相连的节点到源点的距离进行更新
			while(keyIterator.hasNext())
			{
				next= keyIterator.next();
				if(this.visitable.get(next)<temp)
				{
				    u=next;
					temp = this.visitable.get(next);
				}
			}
			this.visited[u]=true;
			//更新和u相连的节点到源点的距离
			updatePathCost(u);
			this.visitable.remove(u);
			this.position++;
			return u;
		}
		else
		{
			return -1;
		}
		
		
	}
	public void updatePathCost(int u)
	{
		float newPathCost;
		EdgeIterator edgeIterator = this.graph.getEdgeIterator(u);//获得所有和u节点相邻的节点集合
		int adjancentNode;
		while(edgeIterator.hasNext())
		{
			adjancentNode = this.graph.getAdjancentNode(edgeIterator.next());
			//将还未被访问的节点进行判断到源点的距离
			if(!this.visited[adjancentNode])
			{
		newPathCost = this.getPathCost(u)+this.graph.getEdgePrestige(this.graph.getEdgeId(adjancentNode, u));
		if(newPathCost<this.getPathCost(adjancentNode))
				{
					this.visitable.put(new Integer(adjancentNode), newPathCost);
					this.pathCost[adjancentNode] = newPathCost;
					this.prev[adjancentNode]=u;
				}
			}
		}
	}
	public float getPathCost(int node)
	{
		return this.pathCost[node];
	}
	public int getPrevNode(int node)
	{
		return this.prev[node];
	}
}

这个优化我已经实现了！需要深入探讨的可以和我联系。希望能够帮助和我以前一样的人！谢谢浏览！