博客

基本原理：层序遍历（队列实现）+堆栈

1.求源点到某个点的最短路径时：一层一层考虑，将源点入队，出队时将与它连接的节点中标记数visit[i]为-1的节点入队，并且每次入队的同时都要更改visit[当前]=visit[上一个节点]+权重；

2.关于解决保存途径点的问题，引入path[]数组和堆栈类型的数组stack[i]，每一个边节点都对应一个path[i]，每个顶点节点都对应一个stack[i]，path[i]里面存放着它(节点i)的上一个节点，当需要输出时，将path依次放入堆栈中再输出。

3.以下为代码实现：

import map.CreateListNDG.EdgeNode;
import map.CreateListNDG.Vertex;
import queue.MyQueue1;
import stack.MyStack;

public class ShortestPath {

	int[] path;
	int[] dist;
	//传入源点参数
	public void unWeighted(Vertex[] vertexList,Vertex s) {
		EdgeNode p;
		MyStack[] myStacks = new MyStack[vertexList.length];
		CreateListNDG createListNDG = new CreateListNDG();
		path = new int[vertexList.length];
		dist = new int[vertexList.length];
		for(int i=0;i<vertexList.length;i++) {
			dist[i] = -1;
			path[i] = 0;
		}
		MyQueue1 queue = new MyQueue1(0, 0, new char[vertexList.length]);
		MyQueue1.enQueue(queue, s.data);
		dist[createListNDG.getPosition(vertexList, s.data)]=0;//入队之后立马将到自己的距离设为0
		while(!MyQueue1.IsEmpty(queue)) {
			char c = MyQueue1.outQueue(queue);
			int position = createListNDG.getPosition(vertexList, c);
			p = vertexList[position].firstEdge;
			while(p != null) {
				int j = createListNDG.getPosition(vertexList, vertexList[p.adjvex].data);
				if(dist[j]==-1) {
					dist[j] = dist[position] + 1;
					path[j] = position;
					MyQueue1.enQueue(queue, vertexList[p.adjvex].data);
				}
				p = p.next;
			}
		}
		for(int i=0;i<vertexList.length;i++) {
			int a = i;
			myStacks[i] = new MyStack(null, null);
			System.out.println("源点"+s.data+"到点"+vertexList[i].data+"的最短距离为"+dist[i]);
			while(path[a] != 0) {
				MyStack.PushStack(myStacks[i], path[a]);
				a = path[a];
			}
			MyStack.PushStack(myStacks[i], createListNDG.getPosition(vertexList, s.data));
		}
		for(int i=0;i<vertexList.length;i++) {
			System.out.print("到"+vertexList[i].data+"最短路径沿途点为：");
			while(!MyStack.IsEmpty(myStacks[i])) {
				int j = MyStack.pupStack(myStacks[i]);
				System.out.print(vertexList[j].data+"->");
			}
			System.out.print(vertexList[i].data);
			System.out.println();
		}
	}
}

简单写个测试类：（注：这里的创建邻接表见我另一篇文章

（java版）用邻接表实现无向图的创建

import map.CreateListNDG.Vertex;

public class Test5 {

	public static void main(String[] args) {
		char[] vexs = {'A','B','C','D','E','F','G','H','I','J','K'};
		char[][] edges = new char[][] {
			{'A','C'},
			{'A','D'},
			{'A','F'},
			{'B','C'},
			{'C','D'},
			{'E','G'},
			{'D','G'},
			{'I','J'},
			{'J','G'},
			{'E','H'},
			{'H','K'},
		};
		CreateListNDG createListNDG = new CreateListNDG();
		Vertex[] vertexList = createListNDG.createListNDG(vexs, edges);
		ShortestPath shortestPath = new ShortestPath();
		shortestPath.unWeighted(vertexList, vertexList[0]);
	}
}