实验三  贪心算法

迪杰斯特拉的贪心算法实现

优先队列等

1.实验目的

1、掌握贪心算法的基本要素 ：最优子结构性质和贪心选择性质

2、应用优先队列求单源顶点的最短路径Dijkstra算法，掌握贪心算法。

2.实验环境

Java

3.问题描述

给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

4.复杂度分析

 Dijkstra算法的时间复杂度为O((m+n)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;List<Integer> path;public Result(int dist, List<Integer> 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]);List<Edge>[] 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];PriorityQueue<Node> 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]));}}}List<Integer> 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, List<Integer> path) {if (u == -1) return;getPath(pre[u], pre, path);path.add(u);}private static class Node implements Comparable<Node> {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;}}
}

输入 

运行

 输出