你的位置:首页 > Java教程

[Java教程]java@ 利用ArrayList构建无向图以及无向图上的dijkstra算法(java.util.ArrayList)


package dataStructure;import java.util.ArrayList;import java.util.Scanner;import java.io.*;class node {  int to, dist;  node(int t, int d) {    to = t;    dist = d;  }}public class Graph {  public static void dfs(ArrayList<ArrayList<node> > map, int v, boolean[] vis) {    vis[v] = true;    System.out.print(v + " ");        ArrayList<node> rhs = map.get(v);    for(int i=0; i<rhs.size(); ++i) {      int nv = rhs.get(i).to;      if(!vis[nv]) dfs(map, nv, vis);    }  }    public static void caseInit(ArrayList<ArrayList<node> > map) {    addEdge(map, 0, 1, 6);    addEdge(map, 1, 2, 2);    addEdge(map, 0, 2, 3);    addEdge(map, 1, 3, 5);    addEdge(map, 2, 3, 3);    addEdge(map, 2, 4, 4);    addEdge(map, 3, 4, 2);    addEdge(map, 3, 5, 3);    addEdge(map, 4, 5, 5);  }    public static void customize(ArrayList<ArrayList<node> > map) {    Scanner input = new Scanner(System.in);    while(true) {      int v = input.nextInt();      if(v == -1) break;             int w = input.nextInt(), d = input.nextInt();       addEdge(map, v, w, d);    }    input.close();  }    public static void addEdge(ArrayList<ArrayList<node> > map, int from, int to, int dist) {    if(from < 0 || from >= map.size() || to < 0 || to >= map.size()) return;        ArrayList<node> rhs = map.get(from);    rhs.add(new node(to, dist));        ArrayList<node> rhs2 = map.get(to);    rhs2.add(new node(from, dist));  }    public static int[] dijkstra(ArrayList<ArrayList<node> > map, int v) {    int[] min_dis = new int[map.size()];    for(int i=0; i<min_dis.length; ++i) min_dis[i] = Integer.MAX_VALUE;    for(int i=0; i<map.get(v).size(); ++i) {      min_dis[map.get(v).get(i).to] = map.get(v).get(i).dist;    }          boolean[] vis = new boolean[map.size()];        min_dis[v] = 0;    vis[v] = true;    ArrayList<node> rhs = map.get(v);        for(int i=1; i<map.size(); ++i) {            int Min = Integer.MAX_VALUE, Minj = v;      for(int j=0; j<map.size(); ++j) {        if(!vis[j] && min_dis[j] < Min) {          Min = min_dis[j];          Minj = j;        }      }            vis[Minj] = true;      ArrayList<node> tmp = map.get(Minj);            for(int k=0; k<tmp.size(); ++k) {        if(!vis[tmp.get(k).to] && min_dis[Minj] + tmp.get(k).dist < min_dis[tmp.get(k).to]) {          min_dis[tmp.get(k).to] = min_dis[Minj] + tmp.get(k).dist;        }      }    }    return min_dis;  }    public static void main(String[] args) {    ArrayList<ArrayList<node> > map = new ArrayList<ArrayList<node> > ();        for(int i=0; i<6; ++i) {      ArrayList<node> row = new ArrayList<node> ();      map.add(row);    }    caseInit(map);        int[] min_dis = dijkstra(map, 0);    for(int i=0; i<min_dis.length; ++i) System.out.print(min_dis[i] + " ");  }}