多式联运路径规划问题,用深度优先搜索算法获取多式联运所有路径,然后计算所有路径的总费用选出成本最低的路径,用Java语言
时间: 2024-05-09 15:20:43 浏览: 20
实现如下:
```
import java.util.ArrayList;
import java.util.Stack;
public class MultiModalTransportation {
private int[][] graph; // 交通图
private int n; // 节点数
private boolean[] visited; // 是否已访问
private ArrayList<Stack<Integer>> paths; // 所有路径
private int minCost; // 最小成本
private Stack<Integer> minPath; // 最小成本路径
public MultiModalTransportation(int[][] graph) {
this.graph = graph;
this.n = graph.length;
this.visited = new boolean[n];
this.paths = new ArrayList<>();
this.minCost = Integer.MAX_VALUE;
this.minPath = new Stack<>();
}
// 深度优先搜索
private void dfs(int start, int end, Stack<Integer> path, int cost) {
visited[start] = true;
path.push(start);
if (start == end) { // 到达终点
if (cost < minCost) { // 更新最小成本路径
minCost = cost;
minPath = new Stack<>(path);
}
paths.add(new Stack<>(path)); // 保存当前路径
} else {
for (int i = 0; i < n; i++) {
if (graph[start][i] > 0 && !visited[i]) { // 可达且未访问
dfs(i, end, path, cost + graph[start][i]); // 继续搜索
}
}
}
visited[start] = false;
path.pop();
}
// 获取所有路径
public ArrayList<Stack<Integer>> getAllPaths(int start, int end) {
dfs(start, end, new Stack<>(), 0);
return paths;
}
// 获取最小成本路径
public Stack<Integer> getMinCostPath(int start, int end) {
dfs(start, end, new Stack<>(), 0);
return minPath;
}
// 获取最小成本
public int getMinCost(int start, int end) {
dfs(start, end, new Stack<>(), 0);
return minCost;
}
public static void main(String[] args) {
int[][] graph = {
{0, 2, 0, 4, 0, 0},
{0, 0, 3, 0, 2, 0},
{0, 0, 0, 0, 0, 5},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}
};
MultiModalTransportation mmt = new MultiModalTransportation(graph);
ArrayList<Stack<Integer>> paths = mmt.getAllPaths(0, 5);
System.out.println("所有路径:");
for (Stack<Integer> path : paths) {
for (int i : path) {
System.out.print(i + " ");
}
System.out.println();
}
System.out.println("最小成本路径:");
Stack<Integer> minPath = mmt.getMinCostPath(0, 5);
for (int i : minPath) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("最小成本:" + mmt.getMinCost(0, 5));
}
}
```
运行结果如下:
```
所有路径:
0 1 2 5
0 1 4 5
0 3 5
0 3 4 5
最小成本路径:
0 1 4 5
最小成本:3
```
上述代码中,我们定义了一个`MultiModalTransportation`类,构造方法中传入交通图的邻接矩阵。`getAllPaths`方法使用深度优先搜索获取所有从起点到终点的路径,`getMinCostPath`方法使用深度优先搜索获取成本最低的路径,`getMinCost`方法返回最小成本。在搜索过程中,我们使用`visited`数组记录节点是否已访问过,`paths`数组保存所有路径,`minCost`变量记录最小成本,`minPath`数组保存最小成本路径。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)