问题描述
我很难解决这个问题。 我有一个.txt文件,其中包含2个城市,并且它们之间的距离以每行分隔。 我的目标是将2个城市设为arg,并找到最短路径。 我创建了3个课程。 主节点,节点和道路(边)。
public class Node {
public Node parent;
public final String cityName;
public double pathCost;
public Road[] neighbors;
public Node(String x){
cityName = x;
}
public String myCity(){
return cityName;
}
}
和
public class Road {
public final double distance;
public final Node destination;
public Road(Node x, double cost){
distance = cost;
destination = x;
}
}
我想知道如何存储节点和边缘。 以下代码是我的尝试。 它似乎可以工作,但是我感觉效率不是很高。
public void initNodes(){
ArrayList<String> cities = new ArrayList<String>();
for(String line : myLines){
String[] split = line.split("\\s+");
if(!cities.contains(split[0]))
{
cities.add(split[0]);
Node n1 = new Node(split[0]);
myNodes.add(n1);
}
if(!cities.contains(split[1]))
{
cities.add(split[1]);
Node n = new Node(split[1]);
myNodes.add(n);
}
}
}
在首先调用该方法为每个城市创建一个Node之后,我调用以下方法来创建Roads。
public void initRoads(){
for(Node n:myNodes){
for(String line : myLines){
String[] split = line.split("\\s+");
if(split[0].equals(n.cityName)){
for(Node n2:myNodes){
if(split[1].equals(n2.cityName)){
Road r1 = new Road(n2,Integer.parseInt(split[2]));
Road r2 = new Road(n,Integer.parseInt(split[2]));
n.neighbors.add(r1);
n2.neighbors.add(r2);
}
}
}
}
}
}
由于所有嵌套的for循环,随着城市和边缘数量的增加,这似乎是不可能的。 有没有一种方法可以解决此问题而无需创建这样的图形? 有没有更简单的方法来创建图形? 谢谢你的帮助。
1楼
乍一看,我认为有几点可以改进:
您指的是每条道路,好像它有
destination
。 您没有特别指出道路是单向道路,因此将道路设置为双向道路是有意义的。您两次浏览文件-为什么? 读完一行后,添加两个城市(或在
Dictionary
找到它们),然后添加道路。对城市而不是列表使用
Dictionary
。 这样,您可以更快地找到城市,并跳过initRoads()
的第一个(和第二个)循环。我还将道路视为具有ID,两个城市和距离的类。 如果需要,每个城市都可以保存与之相连的道路列表。
我不是Java的本地人,但是总体思路应该是这样的:
public class Node {
public Node parent;
public final String cityName;
public double pathCost;
public int[] roads;
public Node(String x){
cityName = x;
}
public String myCity(){
return cityName;
}
}
public class Road {
public final int ID;
public final double distance;
public Road(int id, double cost){
ID = id;
distance = cost;
}
}
public Dictionary<String> cities = new Dictionary<String>();
public void initNodes(){
int curID = 0;
Node first, second;
for(String line : myLines){
String[] split = line.split("\\s+");
first = getNode(split[0]);
second = getNode(split[1]);
Road r1 = new Road(curID,split[2]);
first.roads.add(curID);
second.roads.add(curID);
curID++;
}
}
// Like a singleton...
public void getNode(string cityName){
if(!cities.contains(cityName))
{
Node newCity = new Node(cityName);
cities.add(cityName, newCity);
}
return cities.get(cityName);
}