图求最短路径的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
vertexes = new ArrayList
(); private HashMap
vertexNodeHashMap = new HashMap
(); // protected int[] p; /* 用于存储最短路径下标的数组 */ // protected int[] d ;/* 用于存储到各点最短路径的权值和 */ private int numVertexes; private int numEdges; public ArrayList
> getArcList() { return arcList; } public ArrayList
getVertexes() { return vertexes; } public HashMap
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
al = new ArrayList
(); 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
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); } private static void printPList(int size, int[][] pList) { System.out.println("最短路径的下标P："); for (int v = 0; v < size; ++v) { for (int w = 0; w < size; ++w) { System.out.print(pList[v][w] + "-"); } System.out.println(); } } public static void printDList(int size, int[][] dList) { System.out.println("最短路径的权值和D："); for (int v = 0; v < size; ++v) { for (int w = 0; w < size; ++w) { System.out.print(dList[v][w] + "-"); } System.out.println(); } } public static void printPath(int size, int[][] pList, int[][] dList) { System.out.println("各顶点间最短路径如下:"); for (int v = 0; v < size; ++v) { for (int w = v + 1; w < size; w++) { System.out.println(v + "-" + w + ":" + dList[v][w]); printPathFromV2W(pList, v, w); } } } public static void printPathFromV2W(int[][] pList, int v, int w) { int k; k = pList[v][w]; /* 获得第一个路径顶点下标 */ System.out.print(v + "-"); /* 打印源点 */ while (k != w) /* 如果路径顶点下标不是终点 */ { System.out.print(k + "-"); /* 打印路径顶点 */ k = pList[k][w]; /* 获得下一个路径顶点下标 */ } System.out.println(w); /* 打印终点 */ } }