英文网站建设大概多少钱,企业网站建设咨询,网站开发中职责,重庆市做网站的公司有哪些实验三 贪心算法 迪杰斯特拉的贪心算法实现 优先队列等 1.实验目的
1、掌握贪心算法的基本要素 #xff1a;最优子结构性质和贪心选择性质
2、应用优先队列求单源顶点的最短路径Dijkstra算法#xff0c;掌握贪心算法。
2.实验环境
Java
3.问题描述
给定带权有向图G (V…实验三 贪心算法 迪杰斯特拉的贪心算法实现 优先队列等 1.实验目的
1、掌握贪心算法的基本要素 最优子结构性质和贪心选择性质
2、应用优先队列求单源顶点的最短路径Dijkstra算法掌握贪心算法。
2.实验环境
Java
3.问题描述
给定带权有向图G (V,E)其中每条边的权是非负实数。另外还给定V中的一个顶点称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
4.复杂度分析 Dijkstra算法的时间复杂度为O((mn)logn)其中m是边的数量n是顶点的数量。
5.代码实现
package shiyan3_3;import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;public class DijkstraAlgorithm {public static void main(String[] args) throws IOException {runDijkstraAlgorithm(input.txt, output.txt);}private static class Result {int dist;ListInteger path;public Result(int dist, ListInteger path) {this.dist dist;this.path path;}}public static void runDijkstraAlgorithm(String inputFile, String outputFile) throws IOException {BufferedReader reader new BufferedReader(new FileReader(inputFile));String[] input reader.readLine().split( );int n Integer.parseInt(input[0]);int m Integer.parseInt(input[1]);ListEdge[] graph new List[n 1];for (int i 1; i n; i) {graph[i] new ArrayList();}for (int i 0; i m; i) {input reader.readLine().split( );int u Integer.parseInt(input[0]);int v Integer.parseInt(input[1]);int w Integer.parseInt(input[2]);graph[u].add(new Edge(v, w));}reader.close();int s 1;Result[] results new Result[n 1];PriorityQueueNode pq new PriorityQueue();for (int i 1; i n; i) {if (i s) continue;int[] dist new int[n 1];int[] pre new int[n 1];Arrays.fill(dist, Integer.MAX_VALUE);Arrays.fill(pre, -1);dist[s] 0;pq.offer(new Node(s, 0));while (!pq.isEmpty()) {Node curr pq.poll();if (curr.dist ! dist[curr.u]) continue;for (Edge edge : graph[curr.u]) {int v edge.v;int weight edge.weight;if (dist[v] dist[curr.u] weight) {dist[v] dist[curr.u] weight;pre[v] curr.u;pq.offer(new Node(v, dist[v]));}}}ListInteger path new ArrayList();if (pre[i] ! -1) getPath(i, pre, path);if (path.size() 0) path.add(0, s);results[i] new Result(dist[i], path);}PrintWriter writer new PrintWriter(new FileWriter(outputFile));writer.println(起点\t终点\t最短路径\t\t\t最短路径长度);for (int i 1; i n; i) {if (i s) continue;String res s \t i \t;if (results[i] null || results[i].path.size() 0) {res NA\t\t\tNA;} else {String path results[i].path.stream().map(Object::toString).collect(Collectors.joining(-));int padding 32 - path.length();if (padding 0) path String.format(% padding s, );res path \t results[i].dist;}writer.println(res);}writer.close();System.out.println(输出成功);}private static void getPath(int u, int[] pre, ListInteger path) {if (u -1) return;getPath(pre[u], pre, path);path.add(u);}private static class Node implements ComparableNode {int u;int dist;public Node(int u, int dist) {this.u u;this.dist dist;}Overridepublic int compareTo(Node other) {return Integer.compare(this.dist, other.dist);}}private static class Edge {int v;int weight;public Edge(int v, int weight) {this.v v;this.weight weight;}}
}输入 运行 输出
