本文共 8429 字，大约阅读时间需要 28 分钟。

引子：

Dijkstra算法：某个顶点到其他顶点的最短路径。

以下面这个图为例：其中源点是A。关键点：维护一个二维数组，具体见下面：

1、首先，派一名调查员驻扎在A处，在A处，a调查员能够知道与A相连的B和D的路径长度，在笔记本上记着下面图片1的信息。接下来选择没有驻扎调查员、和A直接相连以及到A路径最短的点。只有B（50）和D（80）直接和A相连，所以选择B。

注意：如果在笔记本上标注了#号的地方，表示已经在此地驻扎了调查员，同时意味着这个就是此地到源点A的最短路径，不会再在笔记本上修改此项。

2、根据上一位调查员的结果，另外派一名调查员驻扎在B处，这样b调查员就知道了与B相连的地点的路径。也就是C和D，致电告诉a调查员，则a调查员在笔记本上记上下面图片2的信息。现在只有A和B才驻扎了调查员，则下面我们应该选择一个与A或B直接相连的、并且到源点A的路径最短的以及没有驻扎调查员的地点。因为A-B-C是110，A到D是80，A-B-D是140，所以另外派一名调查员直接从A到D。

3、d调查员到D地点之后，开始调查，发现了D到E、D到C的路径，致电给a调查员，a调查员做下面如图所示的笔记。

4、这时，只有A、B、D三个地方驻扎了调查员，而与A、B、D直接相连的并且没有驻扎调查员的地点有C、E，所以，接下来就在C、E里面选择他们俩谁离源点A最近，通过比较知道，AC(100)的路径比AE(150)近，所以，接下来另外派一名调查员驻扎到C处、、、、、、

package graph;public class DijkstraGraphTest3 {	public static void main(String[] args) {		MyDijkstraGraph g = new MyDijkstraGraph(40);		//增加顶点		g.addVertex("A");		g.addVertex("B");		g.addVertex("C");		g.addVertex("D");		g.addVertex("E");		g.addVertex("F");		g.addVertex("G");		//增加边和边的权重		g.addEdge(0, 1, 50);		g.addEdge(0, 3, 80);		g.addEdge(1, 2, 60);		g.addEdge(1, 3, 90);		g.addEdge(2, 4, 40);		g.addEdge(3, 2, 20);		g.addEdge(3, 4, 70);		g.addEdge(4, 1, 50);		g.addEdge(2, 5, 60);		g.addEdge(4, 5, 10);		g.addEdge(5, 6, 40);		//执行dijkstra算法		g.doDijkstra();	}}class MyDijkstraGraph{	//最大的权值	private static final int INFINITE = 10000;	//顶点队列	private Vertex[] vertexList;	//邻接矩阵	private int[][] matrix;	//顶点的个数	private int size;	//辅助数组，记录某点的父顶点以及这个点到源点的距离	private DistanceParent[] distanceParents;		public MyDijkstraGraph(int maxSize){		this.vertexList = new Vertex[maxSize];		this.matrix = new int[maxSize][maxSize];		this.size = 0;		this.distanceParents = new DistanceParent[maxSize];	}	//增加顶点	public void addVertex(String label){		vertexList[size++] = new Vertex(label);	}		//增加边和权重	public void addEdge(int start, int end, int weigth){		this.matrix[start][end] = weigth;	}		//执行算法	public void doDijkstra(){		//当前顶点		int currentVertex = 0;		//加入树中的顶点数		int treeNum = 1;				//初始化：把所有的边的权重都为最大		for(int i = 0; i < size; i++){			for(int k = 0; k < size; k++){				int weigth = matrix[i][k];				if(weigth == 0){					matrix[i][k] = INFINITE;				}			}		}		//初始化：第一个顶点到其余顶点的权重，父顶点下标都为0		for(int i = 0; i < size; i++){			int weigth = matrix[currentVertex][i];			distanceParents[i] = new DistanceParent(weigth, 0);		}		//每一次循环，都可以确认某一个顶点到源点的最小距离		while(treeNum < size){			currentVertex = getMin();						//如果成立，说明剩余的顶点没有和当前顶点相连，可以退出了			if(distanceParents[currentVertex].distance == INFINITE){				System.err.println("full ......");				break;			}						vertexList[currentVertex].setInTree(true);						treeNum++;						//打印			print(currentVertex);			//调整辅助数组			adjust(currentVertex);					}			}		/**	 * 获取距离最小的非父顶点的下标	 * @return	 */	public int getMin(){				int temp = INFINITE;		int tempIndex = -1;		for(int i = 0; i < size; i++){			int temp2 = distanceParents[i].distance;			if(temp2 < temp && !vertexList[i].isInTree){				temp = temp2;				tempIndex = i;			}		}		return tempIndex;	}		//调整辅助数组	public void adjust(int currentVertex){				for(int i = 1; i < size; i++){			if(currentVertex == i)				continue;			//当前顶点到边缘顶点的路径长度（权重）			int currentToFringe = matrix[currentVertex][i];			//这个边缘顶点到源点的路径长度（权重）			int startToFringe = distanceParents[currentVertex].distance+currentToFringe;						if(vertexList[i].isInTree == false && distanceParents[i].distance > startToFringe){				distanceParents[i].distance = startToFringe;				distanceParents[i].parentVertex = currentVertex;			}		}	}		public void print(int currentVertex){				Vertex parentVertex = vertexList[distanceParents[currentVertex].parentVertex];				System.out.println(parentVertex.label+" --> "+vertexList[currentVertex].label+							": "+distanceParents[currentVertex].distance+"; ");	}		/**	 *  顶点类	 * @author admin	 *	 */	class Vertex{		//标签		String label;		//是否已经加入树中（即是否已经确认这个顶点到源点的最短路径）		boolean isInTree;				public Vertex(String label){			this.label = label;			this.isInTree = false;		}		public void setInTree(boolean isInTree) {			this.isInTree = isInTree;		}					}		/**	 * 记录某点的父顶点以及这个点到源点的距离	 * @author LiangYH	 *	 */	class DistanceParent{		//从源点到现在所在点的距离		int distance;		//现在所在点的父顶点		int parentVertex;				public DistanceParent(){					}				public DistanceParent(int distance, int parentVertex){			this.distance = distance;			this.parentVertex = parentVertex;		}	}}

二、

下面的代码使用连接矩阵来表示顶点与顶点的边的关系的。具体一点讲就是，有几个顶点就有几行，每一行是一个链表，链表中的元素在实际图中表示为都与同一个元素相连。比如第一行有两个元素B和C，则表示B和C都和A相连。而上面的代码是用邻接矩阵表示的。在内存空间使用方面，本人觉得下面这种方式比较好。

package graph;import java.util.ArrayList;import java.util.Iterator;import java.util.LinkedList;import java.util.List;public class DijkstraGTest {	public static void main(String[] args) {		MyDijkstraG g = new MyDijkstraG(40);		//增加顶点		g.addVertex("A");		g.addVertex("B");		g.addVertex("C");		g.addVertex("D");		g.addVertex("E");		g.addVertex("F");		g.addVertex("G");		//增加边和边的权重		g.addEdge(0, 1, 50);		g.addEdge(0, 3, 80);		g.addEdge(1, 2, 60);		g.addEdge(1, 3, 90);		g.addEdge(2, 4, 40);		g.addEdge(3, 2, 20);		g.addEdge(3, 4, 70);		g.addEdge(4, 1, 50);		g.addEdge(2, 5, 60);		g.addEdge(4, 5, 10);		g.addEdge(5, 6, 40);		//执行dijkstra算法		g.doDijkstra();	}}class MyDijkstraG{	//最大的权值	private static final int INFINITE = 10000;	//二维数组，连接矩阵	List
   
    
     > matrix = null;	//顶点队列	private Vertex[] vertexList;	//顶点的个数	private int size;	//辅助数组，记录某点的父顶点以及这个点到源点的距离	private DistanceParent[] distanceParents;		public MyDijkstraG(int maxSize){		this.vertexList = new Vertex[maxSize];		this.matrix = new ArrayList
     
      
       >();		this.size = 0;		this.distanceParents = new DistanceParent[maxSize];				for(int i = 0; i < maxSize; i++){			LinkedList
       
         list = new LinkedList<>();			matrix.add(list);		}	}	//增加顶点	public void addVertex(String label){		vertexList[size++] = new Vertex(label);	}		//增加边和权重	public void addEdge(int start, int end, int weigth){		VertexWeigth vw = new VertexWeigth(end, weigth);		matrix.get(start).add(vw);	}		//执行算法	public void doDijkstra(){		//当前顶点		int currentVertex = 0;		//加入树中的顶点数		int treeNum = 1;				//初始化：第一个顶点到其余顶点的权重，父顶点下标都为0		Iterator
        
          iter = matrix.get(0).iterator(); while(iter.hasNext()){ VertexWeigth vw = iter.next(); distanceParents[vw.vertexIndex] = new DistanceParent(vw.weigth, 0); } //初始化：把源点不可达的边的权重都为最大,同时防止空异常 for(int i = 0; i < size; i++){ if(distanceParents[i] == null){ distanceParents[i] = new DistanceParent(INFINITE, 0); } } //每一次循环，都可以确认某一个顶点到源点的最小距离 while(treeNum < size){ currentVertex = getMin(); //如果成立，说明剩余的顶点没有和当前顶点相连，可以退出了 if(distanceParents[currentVertex].distance == INFINITE){ System.err.println("full ......"); break; } vertexList[currentVertex].setInTree(true); treeNum++; //打印 print(currentVertex); //调整辅助数组 adjust(currentVertex); } } /** * 获取距离最小的非父顶点的下标 * @return */ public int getMin(){ int temp = INFINITE; int tempIndex = -1; for(int i = 0; i < size; i++){ int temp2 = distanceParents[i].distance; if(temp2 < temp && !vertexList[i].isInTree){ temp = temp2; tempIndex = i; } } return tempIndex; } //调整辅助数组 public void adjust(int currentVertex){ Iterator
         
           iter = matrix.get(currentVertex).iterator(); while(iter.hasNext()){ VertexWeigth vw = iter.next(); int currentToFringe = vw.weigth; int startToFringe = distanceParents[currentVertex].distance+currentToFringe; if(vertexList[vw.vertexIndex].isInTree == false && distanceParents[vw.vertexIndex].distance > startToFringe){ distanceParents[vw.vertexIndex].distance = startToFringe; distanceParents[vw.vertexIndex].parentVertex = currentVertex; } } } public void print(int currentVertex){ Vertex parentVertex = vertexList[distanceParents[currentVertex].parentVertex]; System.out.println(parentVertex.label+" --> "+vertexList[currentVertex].label+ ": "+distanceParents[currentVertex].distance+"; "); } /** * 用于保存尾顶点的下标以及边的权重 * @author LiangYH * */ class VertexWeigth{ int vertexIndex; int weigth; public VertexWeigth(){ } public VertexWeigth(int vertexIndex, int weigth){ this.vertexIndex = vertexIndex; this.weigth = weigth; } } /** * 顶点类 * @author admin * */ class Vertex{ //标签 String label; //是否已经加入树中（即是否已经确认这个顶点到源点的最短路径） boolean isInTree; public Vertex(String label){ this.label = label; this.isInTree = false; } public void setInTree(boolean isInTree) { this.isInTree = isInTree; } } /** * 记录某点的父顶点以及这个点到源点的距离 * @author LiangYH * */ class DistanceParent{ //从源点到现在所在点的距离 int distance; //现在所在点的父顶点 int parentVertex; public DistanceParent(){ } public DistanceParent(int distance, int parentVertex){ this.distance = distance; this.parentVertex = parentVertex; } }}
         
        
       
      
     
    
   

转载地址：https://liangyihuai.blog.csdn.net/article/details/48545419 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！