计算矩阵中非直接连接节点之间的距离
丁勇
问题内容：
问题答案：
我为城市建立了邻接矩阵，并在它们之间建立了联系。例如AB，BC，CD。现在，我想知道是否可以计算未连接的城市之间的距离。是否可以计算未连接节点之间的矩阵距离并找到路径？
城市班
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class GraphCities {
private List<String> cities;
private int[][] matrix;
Scanner s = new Scanner(System.in);
public GraphCities() {
this.cities = new LinkedList<String>();
}
public void addCity(String name) {
if (!cities.contains(name)) {
cities.add(name);
} else {
System.out.println("City " + name + " is already added.");
}
}
public void makeGraph() {
System.out
.println("Distance between cities, if they aren't connected insert -1");
matrix = new int[cities.size()][cities.size()];
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix.length; j++) {
if (i == j) {
matrix[i][j] = 0;
} else {
System.out.println("Distance from "
+ cities.get(i) + " to " + cities.get(j));
int distance = s.nextInt();
matrix[i][j] = distance;
matrix[j][i] = distance;
}
}
}
}
public void show() {
String show = "\t";
for (int i = 0; i < cities.size(); i++) {
show += cities.get(i) + "\t";
}
show += "\n";
for (int i = 0; i < matrix.length; i++) {
show += cities.get(i) + "\t";
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][j] != -1) {
show += matrix[i][j] + "\t";
} else {
show += "-\t";
}
}
show += "\n";
}
System.out.println(show);
}
}
主要方法
public class Main {
public static void main(String[] args) {
GraphCities c = new GraphCities();
c.addCity("A");
c.addCity("B");
c.addCity("C");
c.addCity("D");
c.addCity("E");
c.makeGraph();
System.out.println();
c.show();
}
}
这是我运行main方法时的输出，我认为一切都很好。
A B C D E
A 0 50 - - -
B 50 0 30 - -
C - 30 0 40 -
D - - 40 0 20
E - - - 20 0
现在我想计算从A到D的距离，但我不知道该怎么做。我将不胜感激。谢谢！
问题答案：
要在加权图中找到最短路径（路线的每个部分都有不同的权重），可以使用Dijkstra的最短路径算法。 以下代码是一个文件mcve。可以将其复制粘贴到一个文件（Main.java）中并执行。
（此答案基于编辑问题之前发布的代码）
请注意以下注释：
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Main {
public static void main(String[] args) {
AdjList aList = new AdjList();
CityNode a = new CityNode("A");
CityNode b = new CityNode("B");
CityNode c = new CityNode("C");
CityNode d = new CityNode("D");
CityNode e = new CityNode("E");
aList.addCity(a);
aList.addCity(b);
aList.addCity(c);
aList.addCity(d);
aList.addCity(e);
aList.connectCities(a, b, 50);
aList.connectCities(b, c, 30);
aList.connectCities(c, d, 40);
aList.connectCities(d, e, 20);
aList.show();
FindPath findPath = new FindPath();
System.out.println(findPath.calculateShortestPath(aList, a, e)); //prints 140 as expected
//add some complexity
CityNode f = new CityNode("F");
aList.addCity(f);
aList.connectCities(b, f, 10);
aList.connectCities(f, d, 10);
System.out.println(findPath.calculateShortestPath(aList, a, e));//prints 90 as expected
}
}
class FindPath{
//map to hold distances of all node from origin. at the end this map should contain
//the shortest distance between origin (from) to all other nodes
Map<CityNode, Integer> distances;
//using Dijkstra algorithm
public int calculateShortestPath(AdjList aList, CityNode from, CityNode to) {
//a container to hold which cities the algorithm has visited
Set<CityNode> settledCities = new HashSet<>();
//a container to hold which cities the algorithm has to visit
Set<CityNode> unsettledCities = new HashSet<>();
unsettledCities.add(from);
//map to hold distances of all node from origin. at the end this map should contain
//the shortest distance between origin (from) to all other nodes
distances = new HashMap<>();
//initialize map with values: 0 distance to origin, infinite distance to all others
//infinite means no connection between nodes
for(CityNode city :aList.getCities()){
int distance = city.equals(from) ? 0 : Integer.MAX_VALUE;
distances.put(city, distance);
}
while (unsettledCities.size() != 0) {
//get the unvisited city with the lowest distance
CityNode currentCity = getLowestDistanceCity(unsettledCities);
//remove from unvisited, add to visited
unsettledCities.remove(currentCity); settledCities.add(currentCity);
Map<CityNode, Integer> connectedCities = currentCity.getConnectedCities();
for( CityNode city : connectedCities.keySet()){
//check if new distance is shorted than the previously found distance
if(distances.get(currentCity) + connectedCities.get(city) < distances.get(city)){
//if so, keep the shortest distance found
distances.put(city, distances.get(currentCity) + connectedCities.get(city));
//if city has not been visited yet, add it to unsettledCities
if(! settledCities.contains(city)) {
unsettledCities.add(city);
}
}
}
}
return distances.get(to);
}
private CityNode getLowestDistanceCity(Set <CityNode> unsettledCities) {
return unsettledCities.stream()
.min((c1,c2)-> Integer.compare(distances.get(c1), distances.get(c2)))
.orElse(null);
}
}
class CityNode {
private static int counter =0;
private final String name;
//assign unique id to each node. safer than to rely on unique name
private final int id = counter ++;
//map to hold all connected cities and distance to each
private final Map<CityNode, Integer> connectedCities;
public CityNode(String name) {
super();
this.name = name;
connectedCities = new HashMap<>();
}
public String getName() {
return name;
}
//not null safe. distance must not be negative
public void connect(CityNode connectTo, int distance) {
if(connectTo.equals(this)) throw new IllegalArgumentException("Node can not connect to istself");
connectedCities.put(connectTo, distance);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder(name);
sb.append(connectedCities.keySet().isEmpty() ? " not connected" : " conntected to: " );
for ( CityNode city : connectedCities.keySet()) {
sb.append(city.getName()).append("-")
.append(connectedCities.get(city)).append("km ");
}
return sb.toString();
}
public int getId() {
return id;
}
public Map<CityNode, Integer> getConnectedCities(){
return connectedCities;
}
@Override
public boolean equals(Object o) {
if(o == null ||!(o instanceof CityNode)) return false;
CityNode c = (CityNode) o;
return c.getName().equalsIgnoreCase(name) && id == c.getId();
}
@Override
public int hashCode() {
int hash = 31 * 7 + id;
return name == null ? hash : name.hashCode();
}
}
class AdjList {
//use set which prevents duplicate entries
private final Set<CityNode> citiesList;
public AdjList() {
citiesList = new HashSet<>();
}
//adds city if is not already present. returns true if city was added
public boolean addCity(CityNode city) {
return citiesList.add(city);
}
//not null safe
public void connectCities(CityNode city1, CityNode city2, int distance) {
//assuming undirected graph
city1.connect(city2, distance);
city2.connect(city1, distance);
}
public CityNode getCityByName(String name) {
for (CityNode city : citiesList) {
if (city.getName().equalsIgnoreCase(name))
return city;
}
return null;
}
public void show() {
for (CityNode city : citiesList) {
System.out.println(city);
}
}
//get a copy of cities list
public Collection<CityNode> getCities(){
return new ArrayList<>(citiesList);
}
}
如果您需要getLowestDistanceCity不使用的版本，请Stream使用：
private CityNode getLowestDistanceCity(Set <CityNode> unsettledCities) {
CityNode lowestDistanceCity = null;
int lowestDistance = Integer.MAX_VALUE;
for (CityNode city: unsettledCities) {
int nodeDistance = distances.get(city);
if (nodeDistance < lowestDistance) {
lowestDistance = nodeDistance;
lowestDistanceCity = city;
}
}
return lowestDistanceCity;
}
编辑： 使用邻接矩阵的实现可能如下所示：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class DijkstraAdjacencyMatrix {
public static void main(String[] args) {
Set<CityNode> cities = new HashSet<>();
CityNode a = new CityNode("A");
CityNode b = new CityNode("B");
CityNode c = new CityNode("C");
CityNode d = new CityNode("D");
CityNode e = new CityNode("E");
cities.addAll(List.of(a,b,c,d,e));
CitiesGraph graph = new CitiesGraph(cities);
graph.connectCities(a, b, 50);
graph.connectCities(b, c, 30);
graph.connectCities(c, d, 40);
graph.connectCities(d, e, 20);
graph.show();
FindPath findPath = new FindPath();
System.out.println(findPath.calculateShortestPath(graph, a, e)); //prints 140 as expected
//to add some complexity we need to construct a new CitiesGraph. It is not reusable
CityNode f = new CityNode("F");
cities.add(f);
graph = new CitiesGraph(cities);
graph.connectCities(a, b, 50);
graph.connectCities(b, c, 30);
graph.connectCities(c, d, 40);
graph.connectCities(d, e, 20);
graph.connectCities(b, f, 10);
graph.connectCities(f, d, 10);
graph.show();
System.out.println(findPath.calculateShortestPath(graph, a, e));//prints 90 as expected
}
}
class FindPath{
//map to hold distances of all node from origin. at the end this map should contain
//the shortest distance between origin (from) to all other nodes
Map<CityNode, Integer> distances;
//using Dijkstra algorithm
public int calculateShortestPath(CitiesGraph graph, CityNode from, CityNode to) {
//a container to hold which cities the algorithm has visited
Set<CityNode> settledCities = new HashSet<>();
//a container to hold which cities the algorithm has to visit
Set<CityNode> unsettledCities = new HashSet<>();
unsettledCities.add(from);
//map to hold distances of all node from origin. at the end this map should contain
//the shortest distance between origin (from) to all other nodes
distances = new HashMap<>();
//initialize map with values: 0 distance to origin, infinite distance to all others
//infinite means no connection between nodes
for(CityNode city :graph.getCities()){
int distance = city.equals(from) ? 0 : Integer.MAX_VALUE;
distances.put(city, distance);
}
while (unsettledCities.size() != 0) {
//get the unvisited city with the lowest distance
CityNode currentCity = getLowestDistanceCity(unsettledCities);
//remove from unvisited, add to visited
unsettledCities.remove(currentCity); settledCities.add(currentCity);
Collection<CityNode> connectedCities = graph.getCitiesConnectedTo(currentCity);
//iterate over connected city to update distance to each
for( CityNode city : connectedCities){
//check if new distance is shorted than the previously found distance
int distanceToCity = graph.getDistanceBetween(city, currentCity);
if(distanceToCity <= 0) {
continue;
}
if(distances.get(currentCity) + distanceToCity < distances.get(city)){
//if so, keep the shortest distance found
distances.put(city,distances.get(currentCity) + distanceToCity);
//if city has not been visited yet, add it to unsettledCities
if(! settledCities.contains(city)) {
unsettledCities.add(city);
}
}
}
}
return distances.get(to);
}
private CityNode getLowestDistanceCity(Set <CityNode> unsettledCities) {
return unsettledCities.stream()
.min((c1,c2)-> Integer.compare(distances.get(c1), distances.get(c2)))
.orElse(null);
}
}
class CityNode {
private static int counter =0;
private final String name;
//assign unique id to each node. safer than to rely on unique name
private final int id = counter ++;
public CityNode(String name) {
this.name = name;
}
public String getName() {
return name;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("City ");
sb.append(name).append(" (id=").append(id).append(")");
return sb.toString();
}
public int getId() {
return id;
}
@Override
public boolean equals(Object o) {
if(o == null || !(o instanceof CityNode)) return false;
CityNode c = (CityNode) o;
return c.getName().equalsIgnoreCase(name) && id == c.getId();
}
@Override
public int hashCode() {
int hash = 31 * 7 + id;
return name == null ? hash : name.hashCode();
}
}
class CitiesGraph{
//use set which prevents duplicate entries
private final Set<CityNode> cities;
private final int[][] adjacencyMatrix;
private static final int NOT_CONNECTED = -1;
public CitiesGraph(Set<CityNode> cities) {
this.cities = cities;
adjacencyMatrix = new int[cities.size()][cities.size()];
//initialize matrix
for(int row = 0; row < adjacencyMatrix.length ; row++){
for(int col = 0; col < adjacencyMatrix[row].length ; col++){
adjacencyMatrix[row][col] = row == col ? 0 : NOT_CONNECTED ;
}
}
}
public void connectCities(CityNode city1, CityNode city2, int distance) {
//assuming undirected graph
adjacencyMatrix[city1.getId()][city2.getId()] = distance;
adjacencyMatrix[city2.getId()][city1.getId()] = distance;
}
public int getDistanceBetween(CityNode city1, CityNode city2) {
return adjacencyMatrix[city1.getId()][city2.getId()];
}
public Collection<CityNode> getCitiesConnectedTo(CityNode city) {
Collection<CityNode> connectedCities = new ArrayList<>();
//iterate over row representing city's connections
int column = 0;
for(int distance : adjacencyMatrix[city.getId()]){
if(distance != NOT_CONNECTED && distance > 0) {
connectedCities.add(getCityById(column));
}
column++;
}
return connectedCities;
}
public CityNode getCityById(int id) {
for (CityNode city : cities) {
if (city.getId() == id) return city;
}
return null;
}
public void show() {
for(int[] row : adjacencyMatrix){
System.out.println(Arrays.toString(row));
}
}
//get a copy of cities list
public Collection<CityNode> getCities(){
return new ArrayList<>(cities);
}
}
类似资料：
-
我试图使用Scala类计算两点之间的距离。但它给出了一个错误说 类型不匹配；发现：其他。需要类型（具有基础类型点）：？{def x:？}请注意，隐式转换不适用，因为它们是不明确的：在[A]（x:A）类型的对象Predef中确保[A]的方法any2Ensuring和在[A]（x:A）“ArroAssoc[A]类型的对象Predef中的方法Ani2ArrowasSoc都是可能的其他转换函数。输入到？{
-
问题内容： 我需要创建一个类来计算两点之间的距离。我被困住了，我是一个完全的初学者。这是我的课程： 第二课。 我不确定如何在两个定义的点之间获取点对象（中间点）。 我可以创建点对象，但不确定如何通过位于这两个点对象之间的方法返回点对象。 问题答案： 平面上的两个点（x1，y1）和（x2，y2）之间的距离为： 但是，如果您想要的只是两个点的中点，则应将中点函数更改为： 这将返回一个全新的点对象，其点
-
我对计算两个numpy阵列（x和y）之间的各种空间距离感兴趣。 http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.distance.cdist.html 但是，上述结果会产生太多不需要的结果。我怎样才能限制它只用于我所需的结果。 我想计算[1,11]和[31,41]之间的距离；[2,22]和[32,42
-
我需要计算存储在csr稀疏矩阵和一些点列表中的所有点之间的欧氏距离。对我来说，将csr转换为稠密的csr会更容易，但由于内存不足，我无法将其转换为稠密的csr，因此我需要将其保留为csr。 例如，我有一个数据\u csr稀疏矩阵（csr和稠密视图）： 这个中心点列表： 使用包，data_csr和中心之间的欧几里德距离数组将像下面这样。因此，在center的每行中，总共6个点中的每一个点都是根据da
-
您可以连接两个矩阵以创建更大的矩阵。 方括号'[]'是连接运算符。 MATLAB允许两种类型的连接 - Horizontal concatenation 垂直连接 通过使用逗号分隔两个矩阵来连接两个矩阵时，它们只是水平附加。 它被称为水平连接。 或者，如果通过使用分号分隔两个矩阵来连接两个矩阵，则它们将垂直附加。 它被称为垂直连接。 例子 (Example) 使用以下代码创建脚本文件 - a =
-
问题内容： 我必须计算2个点之间的距离，X和Y是第一个点的坐标，而axisX和axisY是第二个点的坐标。我唯一的线索是此SQL语句，但是此SQL不会返回我要查找的结果。那么，有谁能帮助我确定我在此声明中可能犯的任何错误？ 问题答案： 我假设axisX和axisY是您的坐标。这使用距离计算技术，可以为您提供更准确的读数。 http://www.meridianworlddata.com/Dista