最短路径分为点到点最短路径和源点到其他点的最短路径问题，下面给出广度优先BFS算法的实现。
一、点到点
1.1 问题描述
这里采用迷宫问题来举例。求从起点到终点的最短路径，采用广度优先的顺序，首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径。 由于顶点的最短路径的求解顺序 是一个广度优先的顺序，因此需要一个辅助队列。具体步骤如下： ①从起点开始，先将其加入队列，设置距离为0； ②从队列首端取出位置，将从这个位置能够到达的位置加入队列，并且让这些位置的距离为上一个位置的距离加上1； ③循环2直到将终点添加到队列中，这说明我们已经找到了路径； 在这个过程中，每次处理的位置所对应的距离是严格递增的，因此一旦找到终点，当时的距离就是最短距离。 由此可见，迷宫问题是一个无向无权图。
1.2 算法实现
import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Maze {
static int M, N, dx, dy, gx, gy;
static char[][] a;
static int[][] deep;
public static void main(String[] args) {
Scanner s =
new Scanner(System.in);
System.out.println(
"请输入迷宫的行数：");
M = s.nextInt();
System.out.println(
"请输入迷宫的列数：");
N = s.nextInt();
a =
new char[M][N];
deep =
new int[M][N];
System.out.println(
"请输入迷宫矩阵(起点为'm',终点为'e',墙壁为'1'，可行路径为'0')：");
for (
int i =
0; i < M; i++) {
a[i] = s.next().toCharArray();
}
for (
int i =
0; i < M; i++)
for (
int j =
0; j < N; j++) {
if (a[i][j] ==
'm') {
dx = i;
dy = j;
}
if (a[i][j] ==
'e') {
gx = i;
gy = j;
}
}
int len = bfs();
System.out.println(
"从起点到终点的最短路径为：" + len);
}
private static int bfs() {
Queue<Point> q =
new LinkedList<Point>();
int[] tx = { -
1,
1,
0,
0 };
int[] ty = {
0,
0,
1, -
1 };
q.offer(
new Point(dx, dy));
for (
int i =
0; i < M; i++)
for (
int j =
0; j < N; j++)
deep[i][j] = -
1;
deep[dx][dy] =
0;
while (q.size() >
0) {
Point p = q.poll();
if (p.x == gx && p.y == gy)
break;
for (
int i =
0; i <
4; i++) {
int x = p.x + tx[i];
int y = p.y + ty[i];
if (x >=
0 && x < M && y >=
0 && y < N && a[x][y] !=
'1'
&& deep[x][y] == -
1) {
deep[x][y] = deep[p.x][p.y] +
1;
q.offer(
new Point(x, y));
}
}
}
return deep[gx][gy];
}
}
1.3 算法测试
测试数据为10*10矩阵; 矩阵为： 1111111111 1m01000101 1001000101 1000011001 1011100001 1000100001 1010001001 1011101101 11000000e1 1111111111
运行结果为：
二、源点到其他点
2.1 问题描述
源点的最短路径距离为0，从源点开始，采用广度优先的顺序，首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径。 由于顶点的最短路径的求解顺序、是一个广度优先的顺序，因此需要一个辅助队列。初始时，将源点的最短路径距离设置为0，将源点入队列。 然后，在一个while循环中，从队列中弹出顶点，遍历该顶点的邻接点，若该邻接点的距离未被更新过（表示该邻接点未被访问过），更新邻接点的最短路径距离为该顶点的距离加上1，并将所有的邻接点入队列。 这里采用的图为有向无权图。
2.2 算法实现
class Edge {
String to;
public String
getTo() {
return to;
}
public void setTo(String to) {
this.to = to;
}
Edge nextEdge;
public Edge(String to) {
this.to = to;
this.nextEdge =
null;
}
}
public class Vertex {
String from;
int pathLength =
0;
boolean isVisted =
false;
int indegree;
Edge first;
public boolean getIsVisted() {
return isVisted;
}
public void setIsVisted(
boolean isVisted) {
this.isVisted = isVisted;
}
public String
getFrom() {
return from;
}
public void setFrom(String from) {
this.from = from;
}
public Vertex(String from) {
this.from = from;
first =
null;
this.indegree =
0;
}
public int getPathlength() {
return pathLength;
}
public void setPathlength(
int counter) {
pathLength = counter;
}
}
import java.util.ArrayList;
import java.util.Scanner;
public class Graph {
public Vertex[] v;
public Edge[] e;
public int edgeNumber;
public int vertexNumber;
public void buildGraph() {
Scanner s =
new Scanner(System.in);
System.out.println(
"请输入有向图的顶点数：");
vertexNumber = s.nextInt();
System.out.println(
"请输入有向图的边数：");
edgeNumber = s.nextInt();
v =
new Vertex[vertexNumber];
e =
new Edge[edgeNumber];
System.out.println(
"请输入顶点的名称：");
for (
int i =
0; i < vertexNumber; i++) {
String name = s.next();
v[i] =
new Vertex(name);
}
for (
int i =
0; i < edgeNumber; i++) {
System.out.print(
"输入第" + (i +
1) +
"条有向边的端点A:");
String startVertex = s.next();
System.out.print(
"输入第" + (i +
1) +
"条有向边的端点B:");
String endVertex = s.next();
int vBeginIndex = findvIndex(startVertex);
int vEndIndex = findvIndex(endVertex);
e[i] =
new Edge(endVertex);
v[vEndIndex].indegree++;
e[i].nextEdge = v[vBeginIndex].first;
v[vBeginIndex].first = e[i];
}
}
public int getLength() {
return v.length;
}
public ArrayList<Vertex>
getAdjacentVertex(Vertex ver) {
int index;
ArrayList al =
new ArrayList();
for (
int j =
0; j < v.length; j++) {
if (v[j].first !=
null)
for (Edge e = v[j].first; e !=
null; e = e.nextEdge)
if (e.to.equals(ver.from)) {
al.add(v[j]);
}
}
index = findvIndex(ver.from);
for (Edge e = v[index].first; e !=
null; e = e.nextEdge) {
al.add(v[findvIndex(e.to)]);
}
return al;
}
public int findvIndex(String s) {
int vIndex = -
1;
for (
int j =
0; j < v.length; j++) {
if (v[j].from.equals(s))
vIndex = j;
}
return vIndex;
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class BFS {
Graph g;
public BFS() {
g =
new Graph();
g.buildGraph();
}
public static void main(String[] args) {
BFS s =
new BFS();
System.out.print(
"输入路径的起点：");
Scanner input =
new Scanner(System.in);
String first = input.next();
s.shortestPath(first);
}
public void shortestPath(String first) {
LinkedList<Vertex> queue =
new LinkedList<Vertex>();
Vertex firstVertex = g.v[g.findvIndex(first)];
firstVertex.setIsVisted(
true);
int counter =
0;
firstVertex.setPathlength(counter);
queue.add(firstVertex);
System.out.println(
"最短路径为：");
String path;
while (!queue.isEmpty()) {
Vertex v = queue.poll();
path = v.getFrom();
counter = v.getPathlength();
System.out.println(v.getFrom() +
"的路径长度为 " + v.getPathlength());
ArrayList<Vertex> al = g.getAdjacentVertex(v);
for (Vertex vertex : al) {
if (!(vertex.getIsVisted()))
{
vertex.setIsVisted(
true);
vertex.setPathlength(counter +
1);
queue.add(vertex);
}
}
}
}
}
2.3 算法测试
测试数据为下图：
运行结果为：
