下次自动登录
现在的位置:
& 综合 & 正文
迪杰斯特拉算法处理无向图中最短路径的(dijkstra)Java实现(指定两点，求最短距离及路径)
其实不是原创哈，我写不出来。
如何求图中V0到V5的最短路径呢？
java实现的方式如下：
第一步，根据图来建立权值矩阵：
int[][] W = {
0 } };(-1表示两边不相邻,权值无限大)
例如：W[0][2]=4 表示点V0到点V2的权值为4
W[0][3]=-1表示点V0与V3不相邻，所以权值无限大。
第二步：对V0标号；V0到其它点的路径得到 distance: {0,1,4,-1,-1,-1}; 找到V0到各点中权值最小的那个点（标号的点除外,-1代表无限大），故得到1即对应的下标1，得到V1；对V1标号，然后更改V0通过V1到其它点的路径得到 distance: { 0, 1, 3, 8, 6, -1};
第三步：找到distance中权值最小的那个点，（标号的点除外）得到V2,对V2标号，然后更改V0通过V1-&V2到其它点的路径得到 distance: { 0, 1, 3, 8, 4, -1};
第四步：找到distance中权值最小的那个点，（标号的点除外）得到V4,对V4标号，然后更改V0通过V1-&V2到其它点的路径得到 distance: { 0, 1, 3, 7, 4, 10};
第四步：找到distance中权值最小的那个点，（标号的点除外）得到V3,对V3标号，然后更改V0通过V1-&V2到其它点的路径得到 distance: { 0, 1, 3, 7, 4, 9};
最后只剩下V5没有被标号，就找到V5了。结束！
//这个用来解决无向图中任意两点的最短路径，同时输出路径(起点到所有点的)
public class Success_SQ {public static String dijkstra(int[][] W1, int start, int end) {System.out.println("起点:" + start + "终点:" + end);boolean[] isLabel = new boolean[W1[0].length];// 是否标号int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合，以标号的先后顺序进行存储，实际上是一个以数组表示的栈int i_count = -1;// 栈的顶点int[] distance = W1[start].clone();// v0到各点的最短距离的初始值int index =// 从初始点开始int presentShortest = 0;// 当前临时最短距离
indexs[++i_count] =// 把已经标号的下标存入下标集中isLabel[index] =
while (i_count & W1[0].length) {// 第一步：得到与原点最近的某个点int min = Integer.MAX_VALUE;for (int i = 0; i & distance. i++) {if (!isLabel[i] && distance[i] != -1 && i != index) {// 如果到这个点有边,并且没有被标号if (distance[i] & min) {min = distance[i];index =// 把下标改为当前下标}}}i_count = i_count + 1;if(i_count == W1[0].length){}isLabel[index] =// 对点进行标号indexs[i_count] =// 把已经标号的下标存入下标集中
if (W1[indexs[i_count - 1]][index] == -1|| presentShortest + W1[indexs[i_count - 1]][index] & distance[index]) {// 如果两个点没有直接相连，或者两个点的路径大于最短路径presentShortest = distance[index];} else {presentShortest += W1[indexs[i_count - 1]][index];}// 第二步：加入vi后，重新计算distance中的距离for (int i = 0; i & distance. i++) {
// 如果vi到那个点有边，则v0到后面点的距离加if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达，则现在可达了distance[i] = presentShortest + W1[index][i];} else if (W1[index][i] != -1 && presentShortest + W1[index][i] & distance[i]) {// 如果以前可达，但现在的路径比以前更短，则更换成更短的路径distance[i] = presentShortest + W1[index][i];}
}getRoute(W1,indexs,end);
return "最短距离是：" + (distance[end] - distance[start]);}
public static void main(String[] args) {// 建立一个权值矩阵int[][] W1 = { // 测试数据1{ 0, 1, 4, -1, -1, -1 }, { 1, 0, 2, 7, 5, -1 },{ 4, 2, 0, -1, 1, -1 },{ -1, 7, -1, 0, 3, 2 },{ -1, 5, 1, 3, 0, 6 },{ -1, -1, -1, 2, 6, 0 } };// System.out.println("f" + W1[0][4]);
int[][] W = { // 测试数据2{ 0, 1, 3, 4 },{ 1, 0, 2, -1 },{ 3, 2, 0, 5 }, { 4, -1, 5, 0 } };
System.out.println(dijkstra(W1, 5, 0)); // (int[][] W1, int start, int end)
// indexs:1,0,2,4,3,5 放顶点的顺序// end:最后要的顶点名称:5// routeLength:长度:8/*** seven* 输出路径(起点到所有点的)*/public static String getRoute(int[][] WW, int[] indexs, int end) {String[] routeArray = new String[indexs.length];for (int i = 0; i & routeArray. i++) {routeArray[i] = "";}//自己的路线routeArray[indexs[0]] = indexs[0] + "";for (int i = 1; i & indexs. i++) {//看该点与前面所有点的连接线中的最短路径，然后得到该最短路径到底是连接了哪个点，进而此点的route就是找出那点的route+此点int[] thePointDis = WW[indexs[i]];
int prePoint = 0;int tmp = 9999;for(int j=0;j&thePointDis.j++){boolean chooseFlag =//边的距离最短，而且，所连的点在前面的点当中for(int m=0;m&i;m++){if(j == indexs[m]){chooseFlag =}}if(chooseFlag == false){}if(thePointDis[j] &tmp && thePointDis[j] &0){prePoint =tmp = thePointDis[j];}}routeArray[indexs[i]] = routeArray[prePoint] + indexs[i];}for (int i = 0; i & routeArray. i++) {System.out.println(routeArray[i]);}return "";}
&&&&推荐文章:
【上篇】【下篇】本帖子已过去太久远了，不再提供回复功能。Java实现利用广度优先遍历(BFS)计算最短路径的方法
作者：司青
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了Java实现利用广度优先遍历(BFS)计算最短路径的方法,实例分析了广度优先遍历算法的原理与使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法。分享给大家供大家参考。具体分析如下：
我们用字符串代表图的顶点(vertax)，来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点，然后计算任意两点之间的最短路径。
如下图所示：
如，我想从North Gate去Canteen, 程序的输出结果应为：
BFS: From [North Gate] to [Canteen]:
North Gate
首先定义一个算法接口Algorithm:
public interface Algorithm {
* 执行算法
void perform(Graph g, String sourceVertex);
* 得到路径
Map&String, String& getPath();
然后，定义图:
* (无向)图
public class Graph {
// 图的起点
private String firstV
private Map&String, List&String&& adj = new HashMap&&();
// 遍历算法
public Graph(Algorithm algorithm) {
this.algorithm =
* 执行算法
public void done() {
algorithm.perform(this, firstVertax);
* 得到从起点到{@code vertex}点的最短路径
* @param vertex
public Stack&String& findPathTo(String vertex) {
Stack&String& stack = new Stack&&();
stack.add(vertex);
Map&String, String& path = algorithm.getPath();
for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) {
stack.push(location);
stack.push(firstVertax);
* 添加一条边
public void addEdge(String fromVertex, String toVertex) {
if (firstVertax == null) {
firstVertax = fromV
adj.get(fromVertex).add(toVertex);
adj.get(toVertex).add(fromVertex);
* 添加一个顶点
public void addVertex(String vertex) {
adj.put(vertex, new ArrayList&&());
public Map&String, List&String&& getAdj() {
这里我们使用策略设计模式，将算法与Graph类分离，通过在构造Graph对象时传入一个Algorithm接口的实现来为Graph选择遍历算法。
public Graph(Algorithm algorithm) {
this.algorithm =
无向图的存储结构为邻接表，这里用一个Map表示邻接表，map的key是学校地点(String)，value是一个与该地点相连通的地点表(List&String&)。
private Map&String, List&String&& adj = new HashMap&&();
然后，编写Algorithm接口的BFS实现：
* 封装BFS算法
public class BroadFristSearchAlgorithm implements Algorithm {
// 保存已经访问过的地点
private List&String& visitedV
// 保存最短路径
private Map&String, String&
public void perform(Graph g, String sourceVertex) {
if (null == visitedVertex) {
visitedVertex = new ArrayList&&();
if (null == path) {
path = new HashMap&&();
BFS(g, sourceVertex);
public Map&String, String& getPath() {
private void BFS(Graph g, String sourceVertex) {
Queue&String& queue = new LinkedList&&();
// 标记起点
visitedVertex.add(sourceVertex);
// 起点入列
queue.add(sourceVertex);
while (false == queue.isEmpty()) {
String ver = queue.poll();
List&String& toBeVisitedVertex = g.getAdj().get(ver);
for (String v : toBeVisitedVertex) {
if (false == visitedVertex.contains(v)) {
visitedVertex.add(v);
path.put(v, ver);
queue.add(v);
其中，path是Map类型，意为从 value 到 key 的一条路径。
BFS算法描述：
1. 将起点标记为已访问并放入队列。
2. 从队列中取出一个顶点，得到与该顶点相通的所有顶点。
3. 遍历这些顶点，先判断顶点是否已被访问过，如果否，标记该点为已访问，记录当前路径，并将当前顶点入列。
4. 重复2、3，直到队列为空。
测试用例：
String[] vertex = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"};
Edge[] edges = {
new Edge("North Gate", "Classroom"),
new Edge("North Gate", "Square"),
new Edge("Classroom", "Toilet"),
new Edge("Square", "Toilet"),
new Edge("Square", "Canteen"),
new Edge("Toilet", "South Gate"),
new Edge("Toilet", "South Gate"),
public void testBFS() {
Graph g = new Graph(new BroadFristSearchAlgorithm());
addVertex(g);
addEdge(g);
Stack&String& result = g.findPathTo("Canteen");
System.out.println("BFS: From [North Gate] to [Canteen]:");
while (!result.isEmpty()) {
System.out.println(result.pop());
希望本文所述对大家的java程序设计有所帮助。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具7609人阅读
图论（32）
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
求最短路径步骤　　
算法步骤如下：　　
1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值　　
&&& 若存在&V0,Vi&，d(V0,Vi)为&V0,Vi&弧上的权值　　
&&& 若不存在&V0,Vi&，d(V0,Vi)为∝　
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
&&& 距离值比不加W的路径要短，则修改此距离值　　
&&& 重复上述步骤2、3，直到S中包含所有顶点，即S=T为止
import java.util.*;
public class DjistraPath {
* @param args
* 本题是求从0点到所有点的最短路径
* 每一轮&Find shrotest&都是再找距离0点最近的点v，顾可以知道暂时从0到v的最短距离就是dist[v]，因为如果还有更近的距离，那么v就不是距离0最近的点
* 到找到最近点v后，都要以v为过度点，来比较0-&v-&j和原来记录的路径哪个更近，从而以刷新dist[]
* 当假设除了0点其他，都当过v点的所有情况后，dist[j]数组保留下来的就是从0到j的最短路径
final static int MAXN = 100;
final static int BigNum = ;
static Scanner scan = new Scanner(System.in);
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] graph = new int[MAXN][MAXN];//The Adjacency matrix of the graph
int[] dist = new int[MAXN];//The shortest distence between 0 and N
boolean[] vis= new boolean[MAXN];//Sign the point which is visited
int n,m;//n stands for thm stands for the path
n = scan.nextInt();
m = scan.nextInt();
Arrays.fill(vis, false);
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
graph[i][j] = 0;
graph[i][j] = BigN
int pos1,pos2;
for(int i=0;i&m;i++)
{//Set the date
pos1 = scan.nextInt();
pos2 = scan.nextInt();
graph[pos1][pos2] = scan.nextInt();
for(int i=0;i&n;i++)
//Set the dist[]
dist[i] = graph[0][i];
vis[0] =int min,v = 0;
for(int i=0;i&n-1;i++)
{//Check n-1 times
min = BigN
for(int j=0;j&n;j++)
{//Find shortest
if(vis[j]!= true && dist[j]&min)
{//If the point is not visited and the distence between 0 and j is smallest mark the point j
min = dist[j];
//Sign the point v to be visited
for(int j=0;j&n;j++)
{//Refresh the dist[]
if(vis[j] != true && dist[j]&dist[v]+graph[v][j])
{//when distence is shorter when pass the point v refresh the dist
dist[j] = dist[v] + graph[v][j];
for(int i=0;i&n;i++)
System.out.println(&0-&&+i+&:&+dist[i]);
Test Date:
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：58033次
积分：1052
积分：1052
排名：千里之外
原创：50篇
(1)(4)(1)(19)(25)(1)(3)