经销商问题用Dijkstra算法,六个结点,用Java
时间: 2024-03-24 11:40:15 浏览: 19
以下是使用Dijkstra算法解决经销商问题的Java代码:
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class SalesmanProblemDijkstra {
public static void main(String[] args) {
// 定义经销商问题的图
HashMap<String, HashMap<String, Integer>> graph = new HashMap<>();
graph.put("A", new HashMap<String, Integer>(){{put("B", 2); put("C", 3); put("D", 1);}});
graph.put("B", new HashMap<String, Integer>(){{put("A", 2); put("C", 4); put("D", 2);}});
graph.put("C", new HashMap<String, Integer>(){{put("A", 3); put("B", 4); put("D", 3);}});
graph.put("D", new HashMap<String, Integer>(){{put("A", 1); put("B", 2); put("C", 3);}});
// 计算所有节点之间的最短距离
HashMap<String, Integer> shortestDistances = dijkstra(graph, "A");
// 输出结果
System.out.println(shortestDistances);
}
// 使用Dijkstra算法计算所有节点之间的最短距离
private static HashMap<String, Integer> dijkstra(HashMap<String, HashMap<String, Integer>> graph, String start) {
HashMap<String, Integer> distances = new HashMap<>();
for (String node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(start, 0);
PriorityQueue<String> queue = new PriorityQueue<>((a, b) -> distances.get(a) - distances.get(b));
queue.offer(start);
while (!queue.isEmpty()) {
String currentNode = queue.poll();
for (Map.Entry<String, Integer> neighborEntry : graph.get(currentNode).entrySet()) {
String neighbor = neighborEntry.getKey();
int distance = neighborEntry.getValue();
int newDistance = distances.get(currentNode) + distance;
if (newDistance < distances.get(neighbor)) {
distances.put(neighbor, newDistance);
queue.offer(neighbor);
}
}
}
return distances;
}
}
```
在这个例子中,我们使用了Java的HashMap来存储图的结构,并使用了PriorityQueue来实现Dijkstra算法。我们首先将所有节点的距离初始化为无穷大,然后将起点的距离设为0,并将其加入队列中。接着,我们从队列中取出一个节点,并遍历它的所有邻居节点,计算出新的距离并更新距离表和队列。最终,我们得到了从起点到所有其他节点的最短距离。请注意,这种方法也可以用于解决带权重的最短路径问题。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)