大二暑假java培训第四天
2018.7.3 内容:dijstra的优化
今天上课讲数据库Mysql和JDBC,然而我并不想听,于是选择了刷题。 又碰到了dijstra算法的运用变化,不禁感概,dijstra算法还真能出题。但是每次只有80分左右;然后网上查找了下资料 ,原来dijstra在搜寻当前最短权值还可以优化。就以CCF的201609-4交通规划为例:
这道题就是在dijstra的基础上,更新顶点权值时多加上一个相等的判断条件就可以。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Main {
static int N;
static List<List<Edge>> graph = new ArrayList<>();
static List<Integer> searchOrder = new ArrayList<>();
static boolean[] visited;
static int[] cost;
static int[] path;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();
int M = input.nextInt();
for(int i = 0;i < N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < M; i++){
int firstVertex = input.nextInt();
int nextVertex = input.nextInt();
int weight = input.nextInt();
graph.get(firstVertex - 1).add(new Edge(firstVertex - 1, nextVertex - 1, weight));
graph.get(nextVertex - 1).add(new Edge(nextVertex - 1, firstVertex - 1, weight));
}
dijstra(0);
int sum = 0;
for(int i = 1; i < N; i++)
sum += cost[i];
System.out.println(sum);
}
private static void dijstra(int v) {
path = new int[N];
cost = new int[N];
visited = new boolean[N];
Arrays.fill(path, Integer.MAX_VALUE);
Arrays.fill(visited, false);
path[0] = 0;
while(searchOrder.size() < N){
int u = -1;
int max = Integer.MAX_VALUE;
for(int i = 0; i < N; i++){
if(!visited[i] && path[i] < max){
max = path[i];
u = i;
}
}
visited[u] = true;
searchOrder.add(u);
for(Edge edge: graph.get(u)){
if(!visited[edge.nextVertex]){
if(path[edge.nextVertex] > path[u] + edge.weight){
path[edge.nextVertex] = path[u] + edge.weight;
cost[edge.nextVertex] = edge.weight;
}
else if(path[edge.nextVertex] == path[u] + edge.weight)
cost[edge.nextVertex] = Math.min(cost[edge.nextVertex], edge.weight);
}
}
}
}
public static class Edge{
int firstVertex;
int nextVertex;
int weight;
public Edge(int firstVertex, int nextVertex, int weight){
this.firstVertex = firstVertex;
this.nextVertex = nextVertex;
this.weight = weight;
}
}
static int N;
static List<List<Edge>> graph = new ArrayList<>();
static List<Integer> searchOrder = new ArrayList<>();
static boolean[] visited;
static int[] cost;
static int[] path;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();
int M = input.nextInt();
for(int i = 0;i < N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < M; i++){
int firstVertex = input.nextInt();
int nextVertex = input.nextInt();
int weight = input.nextInt();
graph.get(firstVertex - 1).add(new Edge(firstVertex - 1, nextVertex - 1, weight));
graph.get(nextVertex - 1).add(new Edge(nextVertex - 1, firstVertex - 1, weight));
}
dijstra(0);
int sum = 0;
for(int i = 1; i < N; i++)
sum += cost[i];
System.out.println(sum);
}
private static void dijstra(int v) {
path = new int[N];
cost = new int[N];
visited = new boolean[N];
Arrays.fill(path, Integer.MAX_VALUE);
Arrays.fill(visited, false);
path[0] = 0;
while(searchOrder.size() < N){
int u = -1;
int max = Integer.MAX_VALUE;
for(int i = 0; i < N; i++){
if(!visited[i] && path[i] < max){
max = path[i];
u = i;
}
}
visited[u] = true;
searchOrder.add(u);
for(Edge edge: graph.get(u)){
if(!visited[edge.nextVertex]){
if(path[edge.nextVertex] > path[u] + edge.weight){
path[edge.nextVertex] = path[u] + edge.weight;
cost[edge.nextVertex] = edge.weight;
}
else if(path[edge.nextVertex] == path[u] + edge.weight)
cost[edge.nextVertex] = Math.min(cost[edge.nextVertex], edge.weight);
}
}
}
}
public static class Edge{
int firstVertex;
int nextVertex;
int weight;
public Edge(int firstVertex, int nextVertex, int weight){
this.firstVertex = firstVertex;
this.nextVertex = nextVertex;
this.weight = weight;
}
}
}
结果运行超时。。。下面是用优先队列优化后的代码
package package1;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N;
static List<List<Edge>> graph = new ArrayList<>();
static int[] cost;
static int[] path;
static Queue<Edge> searchOrder = new PriorityQueue<>();
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();
int M = input.nextInt();
for(int i = 0;i < N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < M; i++){
int firstVertex = input.nextInt();
int nextVertex = input.nextInt();
int weight = input.nextInt();
graph.get(firstVertex - 1).add(new Edge(nextVertex - 1, weight));
graph.get(nextVertex - 1).add(new Edge(firstVertex - 1, weight));
}
dijstra(0);
int sum = 0;
for(int i = 1; i < N; i++)
sum += cost[i];
System.out.println(sum);
}
private static void dijstra(int n) {
// TODO Auto-generated method stub
cost = new int[N];
path = new int[N];
Arrays.fill(path, Integer.MAX_VALUE);
path[0] = 0;
searchOrder.offer(new Edge(0,0));
while(!searchOrder.isEmpty()) {
Edge edge = searchOrder.poll();
int v = edge.firstVertex;
if(path[v] < edge.weight){
continue;
}
for(int i = 0; i < graph.get(v).size(); i++){
Edge edge1 = graph.get(v).get(i);
if(path[edge1.firstVertex] > edge1.weight + path[v]){
path[edge1.firstVertex] = edge1.weight + path[v];
searchOrder.offer(new Edge(edge1.firstVertex,path[edge1.firstVertex]));
cost[edge1.firstVertex] = edge1.weight;
}
else if(path[edge1.firstVertex] == edge1.weight + path[v])
cost[edge1.firstVertex] = Math.min(cost[edge1.firstVertex], edge1.weight);
}
}
}
public static class Edge implements Comparable<Edge>{
int firstVertex;
int weight;
public Edge(int firstVertex, int weight){
this.firstVertex = firstVertex;
this.weight = weight;
}
static int N;
static List<List<Edge>> graph = new ArrayList<>();
static int[] cost;
static int[] path;
static Queue<Edge> searchOrder = new PriorityQueue<>();
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
N = input.nextInt();
int M = input.nextInt();
for(int i = 0;i < N; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < M; i++){
int firstVertex = input.nextInt();
int nextVertex = input.nextInt();
int weight = input.nextInt();
graph.get(firstVertex - 1).add(new Edge(nextVertex - 1, weight));
graph.get(nextVertex - 1).add(new Edge(firstVertex - 1, weight));
}
dijstra(0);
int sum = 0;
for(int i = 1; i < N; i++)
sum += cost[i];
System.out.println(sum);
}
private static void dijstra(int n) {
// TODO Auto-generated method stub
cost = new int[N];
path = new int[N];
Arrays.fill(path, Integer.MAX_VALUE);
path[0] = 0;
searchOrder.offer(new Edge(0,0));
while(!searchOrder.isEmpty()) {
Edge edge = searchOrder.poll();
int v = edge.firstVertex;
if(path[v] < edge.weight){
continue;
}
for(int i = 0; i < graph.get(v).size(); i++){
Edge edge1 = graph.get(v).get(i);
if(path[edge1.firstVertex] > edge1.weight + path[v]){
path[edge1.firstVertex] = edge1.weight + path[v];
searchOrder.offer(new Edge(edge1.firstVertex,path[edge1.firstVertex]));
cost[edge1.firstVertex] = edge1.weight;
}
else if(path[edge1.firstVertex] == edge1.weight + path[v])
cost[edge1.firstVertex] = Math.min(cost[edge1.firstVertex], edge1.weight);
}
}
}
public static class Edge implements Comparable<Edge>{
int firstVertex;
int weight;
public Edge(int firstVertex, int weight){
this.firstVertex = firstVertex;
this.weight = weight;
}
@Override
public int compareTo(Edge edge) {
if(this.weight > edge.weight)
return 1;
else if(this.weight < edge.weight)
return -1;
else
return 0;
}
}
public int compareTo(Edge edge) {
if(this.weight > edge.weight)
return 1;
else if(this.weight < edge.weight)
return -1;
else
return 0;
}
}
}
结果正确