Flask接口签名sign原理与实例代码浅析
271
2023-01-14
java实现单源最短路径
本文采用java实现单源最短路径,并带有略微详细的注解,供大家参考,具体内容如下
package com.qf.greaph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
* @author jiayoo
* 7 / 30
* Dijkstra最短路径算法是一种单源最短路径
* 本文采用的是邻接表表示图。
*
* 图的表示: 1. 采用 ArrayList 来储存 图的顶点
* 2. 采用 Map 来储存 边集 , map 可以 实现 一对多的关系, 因此能很好的实现邻接表结构
* 3. 采用ArrayList的原因 是使 边集有序 这样, Node 的里面 那个记录距离的集合才能一一对应
*/
public class MinPath {
private static class graph{
private ArrayList
private Map
private ArrayList
private float[] minPath; //用来存储源点到每个顶点的距离
float min = Float.MAX_VALUE;
/**
* @param start
* @param end
* @param distance
* 构建邻接表。使之成为图
*/
public void addAdjaNode(Node1 start, Node1 end, float distance) {
if (!nodes.contains(start)) {
nodes.add(start);
}
if (!nodes.contains(end)) {
nodes.add(end);
}
if (adjaNode.containsKey(start) && adjaNode.get(start).contains(end)) {
return ;
}
if (adjaNode.containsKey(start)) {
adjaNode.get(start).add(end);
}else {
ArrayList
node.add(end);
adjaNode.put(start, node);
}
start.distonext.add(distance);
}
/**
* 将图打印出来
*/
public void prinGraph() {
if (nodes == null || adjaNode == null) {
System.out.println("图为空");
return ;
}
for (Entry
System.out.println("顶点 : " + entry.getKey().name + " 链接顶点有: ");
for(int i = 0; i < entry.getValue().size(); i++) {
System.out.print(entry.getValue().get(i).name + " " + "距离是: " + entry.getKey().distonext.get(i) + ", ");
}
System.out.println();
}
}
/**
* 1.这个方法用于初始化S集合 及 初始化距离数组
* 2. 设置源点, 并且将源点作为内容 初始化算法
*/
public void findMinPath() {
Node1 node1 = null; // 用来记录列表里最小的点
nodes1 = new ArrayList<>(); // 存储已经遍历过的点
minPath = new float[nodes.size()]; // 初始化距离数组
int i;
/*
* 对最短路径进行初始化, 设置源点到其他地方的值为无穷大
* */
for (i = 0; i < minPath.length; i++) {
minPath[i] = Float.MAX_VALUE;
}
Node1 node = nodes.get(0);
nodes1.add(node); // 将源点加入 S 集合
node.visited = true;
ArrayList
/*
* 先对源节点进行初始化
* 1. 对 距离数组进行初始化。
* 2. 找到源点到某个距离最短的点, 并标记
*
* */
for (i = 0; i < n.size(); i++) {
minPath[n.get(i).id] = node.distonext.get(i); // 最短路径记录
if (min > node.distonext.get(i)) {
min = node.distonext.get(i);
node1 = n.get(i); // 找到当前最短路径
}
}
this.process(node1, min);
}
private void process(Node1 node, float distance ) {
min = Float.MAX_VALUE; //作为标记
Node1 node1 = null; // 同样记录距离最短的点
int i;
ArrayList
for (i = 0 ; i < n.size(); i++) {
if (!n.get(i).visited) { // 这个边集里的顶点不在 S 集合里
if (minPath[n.get(i).id] == Float.MAX_VALUE) {
minPath[n.get(i).id] = distance + node.distonext.get(i); // 源点到下一点的距离
}else if (distance + node.distonext.get(i) < minPath[n.get(i).id] ) { //源点到该顶点的距离变小了, 则改变
minPath[n.get(i).id] = distance + node.distonext.get(i); // 更新源点到下一个点的距离
}
}
}
/*
* 这个for 用于找到 距离集合中 距离源点最近 且并未被访问过的
* 这个for 同时可以确保 该节点确实可到达
* */
for (i = 1; i < minPath.length; i++) {
if (!nodes.get(i).visited) {
if (min > minPath[i] ) {
min = minPath[i];
node1 = nodes.get(i);
}
}
}
if (node1 != null) {
node1.visited = true;
process(node1, min); //源点到 当前的距离
}else { // 说明此位置没有后续节点, 或者 已经全部被访问完了, 则到达此位置只需要加上此位置的值
}
}
}
public static void main(String[] args) {
Node1 n1 = new Node1(0,"A");
Node1 n2 = new Node1(1,"B");
Node1 n3 = new Node1(2,"C");
Node1 n4 = new Node1(3,"D");
Node1 n5 = new Node1(4,"E");
Node1 n6 = new Node1(5,"F");
graph gp = new graph();
gp.addAdjaNode(n1, n2, 6);
gp.addAdjaNode(n2, n1, 6);
gp.addAdjaNode(n1, n3, 3);
gp.addAdjaNode(n3, n1, 3);
gp.addAdjaNode(n2, n3, 2);
gp.addAdjaNode(n3, n2, 2);
gp.addAdjaNode(n2, n4, 5);
gp.addAdjaNode(n4, n2, 5);
gp.addAdjaNode(n3, n4, 3);
gp.addAdjaNode(n4, n3, 3);
gp.addAdjaNode(n3, n5, 4);
gp.addAdjaNode(n5, n3, 4);
gp.addAdjaNode(n4, n5, 2);
gp.addAdjaNode(n5, n4, 2);
gp.addAdjaNode(n4, n6, 3);
gp.addAdjaNode(n6, n4, 3);
gp.addAdjaNode(n5, n6, 5);
gp.addAdjaNode(n6, n5, 5);
// 下面尝试一下非连通图
// /**
// * 权值: 1
// * A -----------B
// * 权 | *
// * 值 | * 权值: 3
// * 2 | *
// * C-----D
// * 权值: 5
// *
// *
// * */
//
// gp.addAdjaNode(n1, n2, 1);
// gp.addAdjaNode(n2, n1, 1);
//
// gp.addAdjaNode(n1, n3, 2);
// gp.addAdjaNode(n3, n1, 2);
//
// gp.addAdjaNode(n1, n4, 3);
// gp.addAdjaNode(n4, n1, 3);
//
// gp.addAdjaNode(n3, n4, 5);
// gp.addAdjaNode(n4, n3, 5);
gp.prinGraph();
System.out.println("--------------------------------------------------------------------");
System.out.println("此数组下标代表id,值代表从源点分别到各点的最短距离, A开始的下标是0, B、C、D等依次类推, 并且源点默认设置为id为零0的开始");
gp.findMinPath();
System.out.println(Arrays.toString(gp.minPath));
}
}
/**
* 顶点类
*/
class Node1{
String name;
boolean visited = false; // 访问状态。有效 减少原算法移除V集合中元素所花费的时间
int id = -1; // 设置默认id为-1
ArrayList
public Node1(int id, String name) {
this.id = id;
this.name = name;
}
}
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~