Мне нужна помощь в добавлении стоимости Edge для моего алгоритма BFS. Я понятия не имею, как добавить стоимость ребра для каждой вершины, добавляемой к пути. Я опубликую код для вашей справки. Дайте мне несколько предложений.
График.java
package algo;
import java.util.*;
public class Graph
{
private static Map<String, LinkedHashSet<HashMap<String, Double>>> map;
private ArrayList<String> nodes = new ArrayList<String>();
private static ArrayList<String> shortestPath = new ArrayList<String>();
public Graph()
{
}
public Graph(String[] nodes)
{
map = new HashMap<String,LinkedHashSet<HashMap<String, Double>>>();
for(int i=0;i<nodes.length;++i)
map.put(nodes[i], new LinkedHashSet<HashMap<String, Double>>());
}
public void addNeighbor(String node1,String node2, Double edgeCost)
{
LinkedHashSet<HashMap<String, Double>> adjacent = map.get(node1);
HashMap<String, Double> innerMap = new HashMap<String, Double>();
if(map.get(node1)==null)
{
adjacent = new LinkedHashSet<HashMap<String, Double>>();
map.put(node1, adjacent);
}
innerMap.put(node2, edgeCost);
adjacent.add(innerMap);
}
public boolean memberOf(String node) {
return nodes.contains(node);
}
public LinkedList<HashMap<String, Double>> getNeighbours(String node) {
LinkedHashSet<HashMap<String, Double>> adjacent = map.get(node);
if(adjacent==null) {
return new LinkedList<HashMap<String, Double>>();
}
return new LinkedList<HashMap<String, Double>>(adjacent);
}
protected void storeNodes(String source, String destination)
{
if (!source.equals(destination))
{
if (!nodes.contains(destination))
{
nodes.add(destination);
}
}
if (!nodes.contains(source)) {
nodes.add(source);
}
}
public void getKeyValuePairs()
{
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext())
{
String key = iterator.next().toString();
LinkedHashSet<HashMap<String, Double>> value = map.get(key);
System.out.println(key + " " + value);
}
}
}
Main.java
package algo;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException
{
File file = new File("city.txt");
FileReader fr = new FileReader(file);
BufferedReader br = new BufferedReader(fr);
String line = br.readLine();
String [] tokens = line.split("\\s+");
String [] nodes = new String[tokens.length];
for (int i = 0; i < nodes.length; ++i) {
nodes[i] = tokens[i];
}
Graph g = new Graph(nodes);
String var_1 = tokens[0];
String var_2 = tokens[1];
Double var_3 = Double.parseDouble(tokens[2]);
g.addNeighbor(var_1, var_2,var_3);
while((line = br.readLine())!=null)
{
tokens = line.split("\\s+");
nodes = new String[tokens.length];
for (int i = 0; i < nodes.length; ++i) {
nodes[i] = tokens[i];
}
//Graph g = new Graph(nodes);
var_1 = tokens[0];
var_2 = tokens[1];
var_3 = Double.parseDouble(tokens[2]);
g.addNeighbor(var_1, var_2,var_3);
g.storeNodes(var_1, var_2);
}
g.getKeyValuePairs();
br.close();
}
}
город.txt
city1 city2 5.5
city1 city3 6
city2 city1 16
city2 city3 26
city2 city4 15.5
city2 city5 7
city3 city4 9
city3 city5 5
city4 city1 3.6
city4 city2 4
city5 city2 7.9
city5 city3 5
это моя часть bfs моего кода, которую я тестировал без добавления каких-либо краевых затрат
public static ArrayList<String> breadthFirstSearch(Graph graph,
String source,
String destination)
{
shortestPath.clear();
// A list that stores the path.
ArrayList<String> path = new ArrayList<String>();
// If the source is the same as destination, I'm done.
if (source.equals(destination) && graph.memberOf(source))
{
path.add(source);
return path;
}
// A queue to store the visited nodes.
ArrayDeque<String> queue = new ArrayDeque<String>();
// A queue to store the visited nodes.
ArrayDeque<String> visited = new ArrayDeque<String>();
queue.offer(source);
while (!queue.isEmpty()) {
String vertex = queue.poll();
visited.offer(vertex);
ArrayList<String> neighboursList = (ArrayList<String>) graph.getNeighbours(vertex);
int index = 0;
int neighboursSize = neighboursList.size();
while (index != neighboursSize) {
String neighbour = neighboursList.get(index);
path.add(neighbour);
path.add(vertex);
if (neighbour.equals(destination)) {
return processPath(source, destination, path);
} else {
if (!visited.contains(neighbour)) {
queue.offer(neighbour);
}
}
index++;
}
}
return null;
}
public static ArrayList<String> processPath(String src,
String destination,
ArrayList<String> path)
{
// Finds out where the destination node directly comes from.
int index = path.indexOf(destination);
String source = path.get(index + 1);
// Adds the destination node to the shortestPath.
shortestPath.add(0, destination);
if (source.equals(src)) {
// The original source node is found.
shortestPath.add(0, src);
return shortestPath;
} else {
// We find where the source node of the destination node
// comes from.
// We then set the source node to be the destination node.
return processPath(src, source, path);
}
}
мой вопрос заключается в том, как добавить граничную стоимость в код в части bfs и указать стоимость пути от источника к месту назначения при выполнении.
