大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 算法——数据结构图的最短路径实现JAVA代码

算法——数据结构图的最短路径实现JAVA代码


[摘要]本文主要是对算法——数据结构图的最短路径实现JAVA代码的讲解,希望对大家学习算法——数据结构图的最短路径实现JAVA代码有所帮助。

  图求最短路径的Floyd和Dijkstra算法JAVA代码实现

  package graph;

  /**

  * Created by Thinkpad on 2014/3/31.

  */

  public class VertexType

  {

  private String name;

  private int id;

  public VertexType(int i, String a)

  {

  id = i;

  name = a;

  }

  public String getName()

  {

  return name;

  }

  public void setName(String name)

  {

  this.name = name;

  }

  public int getId()

  {

  return id;

  }

  public void setId(int id)

  {

  this.id = id;

  }

  }

  package graph;

  /**

  * Created by Thinkpad on 2014/3/31.

  */

  public class EdgeType

  {

  protected int weight;

  public EdgeType(int weight)

  {

  this.weight = weight;

  }

  }

  package graph;

  import java.util.ArrayList;

  import java.util.HashMap;

  public class GraphMatrixOperator

  {

  private static final int INFINITY = 65535;

  private ArrayList> arcList = new ArrayList>();

  private ArrayList<VERTEXTYPE> vertexes = new ArrayList<VERTEXTYPE>();

  private HashMap<STRING, VertexType> vertexNodeHashMap = new HashMap<STRING, VertexType>();

  //    protected  int[] p;    /* 用于存储最短路径下标的数组 */

  //    protected  int[] d ;/* 用于存储到各点最短路径的权值和 */

  private int numVertexes;

  private int numEdges;

  public ArrayList> getArcList()

  {

  return arcList;

  }

  public ArrayList<VERTEXTYPE> getVertexes()

  {

  return vertexes;

  }

  public HashMap<STRING, VertexType> getVertexNodeHashMap()

  {

  return vertexNodeHashMap;

  }

  /* 建立无向网图的邻接矩阵表示 */

  public static void initMGraph(GraphMatrixOperator g)

  {

  }

  protected static void initVertexes(GraphMatrixOperator g)

  {

  for (int i = 0; i < g.numVertexes; i++) /* 读入顶点信息,建立顶点表 */

  {

  g.getVertexes()。set(i, new VertexType(i, ""));

  }

  }

  protected static void initArcWithIJ(GraphMatrixOperator g)

  {

  for (int i = 0; i < g.getNumVertexes(); i++)

  {

  for (int j = i; j < g.getNumVertexes(); j++)

  {

  g.getArcList()。get(j)。get(i)。weight = g.getArcList()。get(i)。get(j)。weight;

  }

  }

  }

  protected static void initNet(GraphMatrixOperator g)

  {

  for (int i = 0; i < g.numVertexes; i++)/* 初始化图 */

  {

  for (int j = 0; j < g.numVertexes; j++)

  {

  if (i == j)

  {

  g.getArcList()。get(i)。set(j, new EdgeType(0));

  }

  else

  {

  g.getArcList()。get(i)。set(j, new EdgeType(INFINITY));

  g.getArcList()。get(j)。set(i, new EdgeType(INFINITY));

  }

  }

  }

  }

  private static void initArcList(GraphMatrixOperator g, int size)

  {

  for (int i = 0; i < size; i++)

  {

  ArrayList<EDGETYPE> al = new ArrayList<EDGETYPE>();

  g.getArcList()。add(al);

  for (int j = 0; j < size; j++)

  {

  if (i == j)

  {

  al.add(new EdgeType(0));

  }

  else

  {

  al.add(new EdgeType(INFINITY));

  }

  }

  }

  }

  public static void addArcFromI2J(GraphMatrixOperator g, String a, String b, int w)

  {

  addVex(g, a);

  addVex(g, b);

  g.getArcList()。get(g.getVertexNodeHashMap()。get(a)。getId())。get(g.getVertexNodeHashMap()。get(b)。getId())。weight = w;

  g.getArcList()。get(g.getVertexNodeHashMap()。get(b)。getId())。get(g.getVertexNodeHashMap()。get(a)。getId())。weight = w;

  }

  private static void addVex(GraphMatrixOperator g, String a)

  {

  if (!g.getVertexNodeHashMap()。containsKey(a))

  {

  int size = g.getVertexes()。size();

  VertexType e = new VertexType(size, a);

  g.getVertexes()。add(e);

  g.getVertexNodeHashMap()。put(a, e);

  }

  }

  /*  Dijkstra算法,求有向网G的v0顶点到其余顶点v的最短路径p[v]及带权长度d[v] */

  /*  p[v]的值为前驱顶点下标,d[v]表示v0到v的最短路径长度和 */

  public static void shortestPath_Dijkstra(GraphMatrixOperator g, int v0, int[] p, int[] d)

  {

  int v, w, k = 0, min;

  int maxvex = g.getNumVertexes();

  int[] finalInt = new int[maxvex];/* finalInt[w]=1表示求得顶点v0至vw的最短路径 */

  int n = g.numVertexes;

  for (v = 0; v < n; v++)    /* 初始化数据 */

  {

  finalInt[v] = 0;            /* 全部顶点初始化为未知最短路径状态 */

  d[v] = g.getArcList()。get(v0)。get(v)。weight;/* 将与v0点有连线的顶点加上权值 */

  p[v] = -1;              /* 初始化路径数组P为-1  */

  }

  d[v0] = 0;  /* v0至v0路径为0 */

  finalInt[v0] = 1;    /* v0至v0不需要求路径 */

  /* 开始主循环,每次求得v0到某个v顶点的最短路径 */

  for (v = 1; v < n; v++)

  {

  min = INFINITY;    /* 当前所知离v0顶点的最近距离 */

  for (w = 0; w < n; w++) /* 寻找离v0最近的顶点 */

  {

 

  if ((finalInt[w] == 0) && (d[w] < min))

  {

  k = w;

  min = d[w];    /* w顶点离v0顶点更近 */

  }

  }

  finalInt[k] = 1;    /* 将目前找到的最近的顶点置为1 */

  for (w = 0; w < n; w++) /* 修正当前最短路径及距离 */

  {

  /* 如果经过v顶点的路径比现在这条路径的长度短的话 */

  if ((0 == finalInt[w]) && ((min + g.getArcList()。get(k)。get(w)。weight) < d[w]))

  { /*  说明找到了更短的路径,修改d[w]和p[w] */

  d[w] = min + g.getArcList()。get(k)。get(w)。weight;  /* 修改当前路径长度 */

  p[w] = k;

  }

  }

  }

  System.out.println("final[]:");

  for (int i : finalInt)

  {

  System.out.print(i);

  }

  System.out.println();

  }

  public static void main(String[] args)

  {

  /* 求某点到其余各点的最短路径 */

  String[] src = new String[]{"a,b,1", "b,c,2", "a,c,4", "b,d,7"};

  GraphMatrixOperator g = createMGraph(src);

  logMGraph(g);

  int v0 = 0;

  main_Dijkstra(g, v0);

  main_floyd(g);

  }

  private static GraphMatrixOperator createMGraph(String[] src)

  {

  GraphMatrixOperator g = new GraphMatrixOperator();

  initArcList(g, src.length);

  for (String s : src)

  {

  System.out.println(s);

  String[] line = s.split(",");

  addArcFromI2J(g, line[0], line[1], Integer.valueOf(line[2]));

  }

  int size = g.getVertexes()。size();

  g.setNumVertexes(size);

  g.setNumEdges(src.length);

  return g;

  }

  private static void logMGraph(GraphMatrixOperator g)

  {

  for (VertexType vertexType : g.getVertexes())

  {

  System.out.print(vertexType.getName() + " ");

  }

  System.out.println();

  for (ArrayList<EDGETYPE> edgeTypes : g.getArcList())

  {

  for (EdgeType edgeType : edgeTypes)

  {

  System.out.print(edgeType.weight + "  ");

  }

  System.out.println();

  }

  }

  private static void main_Dijkstra(GraphMatrixOperator g, int v0)

  {

  int size = g.getVertexes()。size();

  int[] p = new int[size];

  int[] d = new int[size];

  shortestPath_Dijkstra(g, v0, p, d);

  System.out.println("用于存储到各点最短路径的权值和:");

  for (int i : d)

  {

  System.out.print(i + " ");

  }

  System.out.println();

  System.out.println("用于存储最短路径下标的数组 :");

  for (int i : p)

  {

  System.out.print(i + " ");

  }

  System.out.println();

  System.out.println("最短路径倒序如下:");

  int j;

  for (int i = 1; i < g.numVertexes; ++i)

  {

  System.out.print(v0 + "-" + i + ":");

  j = i;

  while (p[j] != -1)

  {

  System.out.print(g.getVertexes()。get(p[j])。getName());

  j = p[j];

  }

  System.out.println();

  }

  System.out.println("\n源点到各顶点的最短路径长度为:");

  for (int i = 1; i < g.numVertexes; ++i)

  {

  System.out.print(g.getVertexes()。get(v0)。getName() + "-");

  System.out.print(g.getVertexes()。get(i)。getName() + ":");

  System.out.println(d[i]);

  }

  }

  public void setNumVertexes(int numVertexes)

  {

  this.numVertexes = numVertexes;

  }

  public int getNumVertexes()

  {

  return numVertexes;

  }

  public void setNumEdges(int numEdges)

  {

  this.numEdges = numEdges;

  }

  public int getNumEdges()

  {

  return numEdges;

  }

  /* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径p[v][w]及带权长度d[v][w]. */

  public static void shortestPath_Floyd(GraphMatrixOperator g, int[][] pList, int[][] dList)

  {

  int size = g.numVertexes;

  for (int v = 0; v < size; ++v) /* 初始化D与P */

  {

  for (int w = 0; w < size; ++w)

  {

  dList[v][w] = g.arcList.get(v)。get(w)。weight;   /* d[v][w]值即为对应点间的权值 */

  pList[v][w] = w;                /* 初始化P */

  }

  }

  for (int k = 0; k < size; ++k)

  {

  for (int v = 0; v < size; ++v)

  {

  for (int w = 0; w < size; ++w)

  {

  if (dList[v][w] > dList[v][k] + dList[k][w])

  {/* 如果经过下标为k顶点路径比原两点间路径更短 */

  dList[v][w] = dList[v][k] + dList[k][w];/* 将当前两点间权值设为更小的一个 */

  pList[v][w] = pList[v][k];/* 路径设置为经过下标为k的顶点 */

  }

  }

  }

  }

  }

  public static void main_floyd(GraphMatrixOperator g)

  {

  int size = g.getVertexes()。size();

  int[][] pList = new int[size][size];

  int[][] dList = new int[size][size];

  shortestPath_Floyd(g, pList, dList);

  printPath(size, pList, dList);

  printDList(size, dList);

  printPList(size, pList);

  }



相关评论