Dijkstra迪杰斯特拉算法JAVA

Dijkstra 迪杰斯特拉算法的 JAVA实现

package homework2;

public class Find {
	MapArray map;
	int startPoint;
	int endPoint;
	NowShortest nowShortest;
	int nowPoint;
	
	public Find（MapArray mapint startPointint endPoint）{
		this.map=map;
		this.startPoint=startPoint;
		this.endPoint=endPoint;
		this.nowShortest=new NowShortest（map.pointNum）;
		nowPoint=startPoint;
	}
	
	public void FindShortest（）{
		//标记该点已选
		nowShortest.shortestLinesValue[1][nowPoint]=0;
		//初始化起始节点
		nowShortest.firstShortestLine[nowPoint].next=new Node（map.pointNum）;
		nowShortest.firstShortestLine[nowPoint].next.pre=nowShortest.firstShortestLine[nowPoint].next;
		nowShortest.firstShortestLine[nowPoint].next.array[0]=nowPoint;
		nowShortest.firstShortestLine[nowPoint].isTheEnd=false;
		
		
		for（int i=0;i			
			nowShortest.shortestLinesValue[0][nowPoint]=1;
			for（int j=0;j				int theValue;
				if（map.theMap[nowPoint][j]!=0）{
					theValue=map.theMap[nowPoint][j];
				}
				else {
					theValue=300;//大于预设的200
				}
				if（nowShortest.shortestLinesValue[1][nowPoint]+theValue
											
					SetTheLine（nowShortest.firstShortestLine[nowPoint].next
							nowShortest.firstShortestLine[j]j）; 

					nowShortest.shortestLinesValue[1][j]=
							nowShortest.shortestLinesValue[1][nowPoint]+theValue;
				}
				else if（nowShortest.shortestLinesValue[1][nowPoint]+theValue
						==nowShortest.shortestLinesValue[1][j]）{
					//找出原链表最后一个节点
					Node currentNode=nowShortest.firstShortestLine[j];
					while（currentNode.isTheEnd==false）{
						currentNode=currentNode.next;
					}
					SetTheLine（nowShortest.firstShortestLine[nowPoint].nextcurrentNodej）;
					
				}
				else{
					
				}	
			}
			int MinValue=200;
			int MinPoint=0;
			for（int k=0;k				if（nowShortest.shortestLinesValue[0][k]==0）{
					if（nowShortest.shortestLinesValue[1][k]						MinValue=nowShortest.shortestLinesValue[1][k];
						MinPoint=k;
					}
					else{
						
					}
				}
				else{
					
				}
			}
			nowPoint=MinPoint;	
			
		}
		Print（）;
	}
	
	
	
	//currentNode为当前节点的最短路径链表第一个有效节点
	//newLinePreNode为更新节点的最短路径链表的首节点
	public void SetTheLine（Node currentNodeNode newLinePreNodeint pointNum）{
		Node newLineCurrentNode;
		//将更新的值保存在链表中
		while（currentNode.isTheEnd==false）{
			Node node=new Node（map.pointNum）;
			for（int k=0;k				if（currentNode.array[k]!=-1）{
					node.array[k]=currentNode.array[k];
				}
				else{
					node.array[k]=pointNum;
					break;
				}
			}
			newLineCurrentNode=node;
			newLineCurrentNode.pre=newLinePreNode;
			newLinePreNode.next=newLineCurrentNode;
			newLinePreNode.isTheEnd=false;
			newLinePreNode=newLineCurrentNode;
			currentNode=currentNode.next;
		}
		
		Node node=new Node（map.pointNum）;
		for（int k=0;k			if（currentNode.array[k]!=-1）{
				node.array[k]=c

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6921  2013-04-15 14:20  Dijkstra迪杰斯特拉算法JAVA\Find.java

     文件       1606  2013-04-16 09:39  Dijkstra迪杰斯特拉算法JAVA\Main.java

     文件        415  2013-04-11 17:56  Dijkstra迪杰斯特拉算法JAVA\MapArray.java

     文件        230  2013-04-13 11:57  Dijkstra迪杰斯特拉算法JAVA\Node.java

     文件        419  2013-04-12 19:09  Dijkstra迪杰斯特拉算法JAVA\NowShortest.java

     目录          0  2013-04-22 17:06  Dijkstra迪杰斯特拉算法JAVA

----------- ---------  ---------- -----  ----

                 9591                    6