Java期末课程设计 (最短路径推荐程序）

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;

class Edge implements Comparable<Edge> {
  int to, cost;

  Edge(int to_, int cost_) {
    to = to_;
    cost = cost_;
  }

  @Override
  public int compareTo(Edge o) {
    return this.cost - o.cost;
  }
}

class Main extends JFrame {
  static int maxn = 10005;
  static int pre[];
  static int dis[];
  static int p[];  
  static int cnt = 0;
  static Map<String, Integer> map = new HashMap<String, Integer>();
  static ArrayList<ArrayList<Edge>> e;
  static p[] b = new p[1005];
  static String pos[];

  public static void init() {
    for (int i = 0; i < 1005; i++) {
      b[i] = new p();
    }
    pos = new String[1000];
    b[1].x = 300;
    b[1].y = 10;
    b[1].h = 500;
    b[1].w = 20;
    b[2].x = 450;
    b[2].y = 80;
    b[2].h = 100;
    b[2].w = 50;
    b[3].x = 250;
    b[3].y = 120;
    b[3].h = 100;
    b[3].w = 100;
    b[4].x = 460;
    b[4].y = 250;
    b[4].h = 120;
    b[4].w = 50;
    b[5].x = 620;
    b[5].y = 90;
    b[5].h = 80;
    b[5].w = 50;
    b[6].x = 200;
    b[6].y = 480;
    b[6].h = 90;
    b[6].w = 150;
    b[7].x = 300;
    b[7].y = 250;
    b[7].h = 90;
    b[7].w = 250;
    b[8].x = 530;
    b[8].y = 330;
    b[8].h = 80;
    b[8].w = 50;
    b[9].x = 530;
    b[9].y = 400;
    b[9].h = 80;
    b[9].w = 50;
    b[10].x = 630;
    b[10].y = 200;
    b[10].h = 100;
    b[10].w = 440;
    b[11].x = 350;
    b[11].y = 630;
    b[11].h = 220;
    b[11].w = 100;
    map.put("长江路", 1);
    map.put("北门", 2);
    map.put("教学楼", 3);
    map.put("图书馆", 4);
    map.put("行政楼", 5);
    map.put("学苑餐厅", 6);
    map.put("学生宿舍", 7);
    map.put("小餐厅", 8);
    map.put("科技苑", 9);
    map.put("体育馆", 10);
    map.put("下沉广场", 11);
    e = new ArrayList<ArrayList<Edge>>();
    for (int i = 0; i < maxn; i++) {
      ArrayList<Edge> temp = new ArrayList<Edge>();
      e.add(temp);
    }

    int u, v, cost;
    int x1 = (b[1].x + b[1].h) / 2;
    int y1 = (b[1].y + b[1].w) / 2;
    int x2 = (b[2].x + b[2].h) / 2;
    int y2 = (b[2].y + b[2].w) / 2;
    u = 1;
    v = 2;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[2].x + b[2].h) / 2;
    y1 = (b[2].y + b[2].w) / 2;
    x2 = (b[3].x + b[3].h) / 2;
    y2 = (b[3].y + b[3].w) / 2;
    u = 2;
    v = 3;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[2].x + b[2].h) / 2;
    y1 = (b[2].y + b[2].w) / 2;
    x2 = (b[4].x + b[4].h) / 2;
    y2 = (b[4].y + b[4].w) / 2;
    u = 2;
    v = 4;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[2].x + b[2].h) / 2;
    y1 = (b[2].y + b[2].w) / 2;
    x2 = (b[5].x + b[5].h) / 2;
    y2 = (b[5].y + b[5].w) / 2;
    u = 2;
    v = 5;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[2].x + b[2].h) / 2;
    y1 = (b[2].y + b[2].w) / 2;
    x2 = (b[10].x + b[10].h) / 2;
    y2 = (b[10].y + b[10].w) / 2;
    u = 2;
    v = 10;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[3].x + b[3].h) / 2;
    y1 = (b[3].y + b[3].w) / 2;
    x2 = (b[7].x + b[7].h) / 2;
    y2 = (b[7].y + b[7].w) / 2;
    u = 3;
    v = 7;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[3].x + b[3].h) / 2;
    y1 = (b[3].y + b[3].w) / 2;
    x2 = (b[4].x + b[4].h) / 2;
    y2 = (b[4].y + b[4].w) / 2;
    u = 3;
    v = 4;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[3].x + b[3].h) / 2;
    y1 = (b[3].y + b[3].w) / 2;
    x2 = (b[10].x + b[10].h) / 2;
    y2 = (b[10].y + b[10].w) / 2;
    u = 3;
    v = 10;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[5].x + b[5].h) / 2;
    y1 = (b[5].y + b[5].w) / 2;
    x2 = (b[10].x + b[10].h) / 2;
    y2 = (b[10].y + b[10].w) / 2;
    u = 5;
    v = 10;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[4].x + b[4].h) / 2;
    y1 = (b[4].y + b[4].w) / 2;
    x2 = (b[8].x + b[8].h) / 2;
    y2 = (b[8].y + b[8].w) / 2;
    u = 4;
    v = 8;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[4].x + b[4].h) / 2;
    y1 = (b[4].y + b[4].w) / 2;
    x2 = (b[9].x + b[9].h) / 2;
    y2 = (b[9].y + b[9].w) / 2;
    u = 4;
    v = 9;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[7].x + b[7].h) / 2;
    y1 = (b[7].y + b[7].w) / 2;
    x2 = (b[6].x + b[6].h) / 2;
    y2 = (b[6].y + b[6].w) / 2;
    u = 7;
    v = 6;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[6].x + b[6].h) / 2;
    y1 = (b[6].y + b[6].w) / 2;
    x2 = (b[11].x + b[11].h) / 2;
    y2 = (b[11].y + b[11].w) / 2;
    u = 6;
    v = 11;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[8].x + b[8].h) / 2;
    y1 = (b[8].y + b[8].w) / 2;
    x2 = (b[10].x + b[10].h) / 2;
    y2 = (b[10].y + b[10].w) / 2;
    u = 8;
    v = 10;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[9].x + b[9].h) / 2;
    y1 = (b[9].y + b[9].w) / 2;
    x2 = (b[10].x + b[10].h) / 2;
    y2 = (b[10].y + b[10].w) / 2;
    u = 9;
    v = 10;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));

    x1 = (b[9].x + b[9].h) / 2;
    y1 = (b[9].y + b[9].w) / 2;
    x2 = (b[8].x + b[8].h) / 2;
    y2 = (b[8].y + b[8].w) / 2;
    u = 8;
    v = 9;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));
    x1 = (b[9].x + b[9].h) / 2;
    y1 = (b[9].y + b[9].w) / 2;
    x2 = (b[11].x + b[11].h) / 2;
    y2 = (b[11].y + b[11].w) / 2;
    u = 11;
    v = 9;
    cost = qdis(x1, y1, x2, y2);
    e.get(u).add(new Edge(v, cost));
    e.get(v).add(new Edge(u, cost));

  }

  public static void dijkstra(int s) {
    int vis[] = new int[maxn];
    dis = new int[maxn];
    pre = new int[maxn];
    for (int i = 1; i < maxn; i++) {
      dis[i] = 2147483647;
      pre[i] = -1;
    }
    Queue<Edge> q = new PriorityQueue<>();
    q.add(new Edge(s, 0));
    dis[s] = 0;
    while (q.isEmpty() == false) {
      Edge now = q.poll();
      int u = now.to;
      vis[u] = 0;
      for (int i = 0; i < e.get(u).size(); i++) {
        int v = e.get(u).get(i).to;
        int cost = e.get(u).get(i).cost;
        if (dis[v] > dis[u] + cost) {
          dis[v] = dis[u] + cost;
          pre[v] = u;
          if (vis[v] == 0) {
            q.add(new Edge(v, dis[v]));
            vis[v] = 1;
          }
        }
      }
    }
  }

  public static int qdis(int x1, int y1, int x2, int y2) {
    return (int) Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }

  public static void solve(String s, String se) {

    dijkstra(map.get(s));
    cnt = 0;
    p = new int[55 + 5];
    for (int i = map.get(se); i != -1; i = pre[i]) {
      p[cnt++] = i;
    }
  }

  public static void main(String[] args) {
    Main.init();
    new draw().setVisible(true);
  }
}

class p {
  int x, y, h, w;
}

class draw extends Main {
  public draw() {
    setTitle("南阳理工老校区简图");
    setSize(900, 800);
    setLayout(null);
    JButton b1 = new JButton("长江路");
    JButton b2 = new JButton("北门");
    JButton b3 = new JButton("教学楼");
    JButton b4 = new JButton("图书馆");
    JButton b5 = new JButton("行政楼");
    JButton b6 = new JButton("学苑餐厅");
    JButton b7 = new JButton("学生宿舍");
    JButton b8 = new JButton("小餐厅");
    JButton b9 = new JButton("科技苑");
    JButton b10 = new JButton("体育馆");
    JButton b11 = new JButton("下沉广场");
    b1.setBounds(300, 10, 500, 20);
    b4.setBounds(460, 250, 120, 50);
    b11.setBounds(350, 630, 220, 100);
    b8.setBounds(530, 330, 80, 50);
    b9.setBounds(530, 400, 80, 50);
    b10.setBounds(630, 200, 100, 440);
    b2.setBounds(450, 80, 100, 50);
    b5.setBounds(620, 90, 80, 50);
    b3.setBounds(250, 120, 100, 100);
    b7.setBounds(300, 250, 90, 250);
    b6.setBounds(200, 480, 90, 150);
    add(b1);
    add(b2);
    add(b3);
    add(b4);
    add(b5);
    add(b6);
    add(b7);
    add(b8);
    add(b9);
    add(b10);
    add(b11);
    JLabel label = new JLabel();
    label.setBounds(20, 150, 200, 50);
    JTextField value = new JTextField();
    value.setBounds(100, 75, 100, 30);
    JLabel l1 = new JLabel("起点:");
    l1.setBounds(20, 20, 80, 30);
    JLabel l2 = new JLabel("终点:");
    l2.setBounds(20, 75, 80, 30);
    JButton b = new JButton("搜索");
    b.setBounds(100, 120, 100, 30);
    JTextField text = new JTextField();
    text.setBounds(100, 20, 100, 30);
    add(value);
    add(l1);
    add(label);
    add(l2);
    add(b);
    add(text);
    setLocationRelativeTo(null);
    setLayout(null);
    setVisible(true);
    b.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent e) {
        String s1 = text.getText();
        String s2 = value.getText();
        solve(s1, s2);
        label.setText(s1 + " ---> " + s2 + " 最短距离 " + dis[map.get(s2)] + " m");
        repaint();

      }
    });
    setDefaultCloseOperation(EXIT_ON_CLOSE);
    setLocationRelativeTo(null);
  }

  public void paint(Graphics g) {
    g.clearRect(0, 0, 900, 800);
    super.paint(g);
    setLayout(null);
    Graphics2D g2 = (Graphics2D) g;
    g2.setStroke(new BasicStroke(1.5f));
    g2.setColor(Color.red);
    for (int i = 1; i < cnt; i++) {
      int x = (b[p[i - 1]].x + b[p[i - 1]].h / 2);
      int y = (b[p[i - 1]].y + b[p[i - 1]].w / 2 + 10);
      int xx = (b[p[i]].x + b[p[i]].h / 2 + 10);
      int yy = (b[p[i]].y + b[p[i]].w / 2 + 10);
      g2.drawLine(x, y, xx, yy);
    }

  }
}