当前比较行：0，shortTablePath结果：[0, 1, 5, 1000, 1000, 1000, 1000, 1000, 1000]
当前比较行：1，shortTablePath结果：[0, 1, 4, 8, 6, 1000, 1000, 1000, 1000]
当前比较行：2，shortTablePath结果：[0, 1, 4, 8, 5, 11, 1000, 1000, 1000]
当前比较行：4，shortTablePath结果：[0, 1, 4, 7, 5, 8, 11, 14, 1000]
当前比较行：3，shortTablePath结果：[0, 1, 4, 7, 5, 8, 10, 14, 1000]
当前比较行：5，shortTablePath结果：[0, 1, 4, 7, 5, 8, 10, 13, 1000]
当前比较行：6，shortTablePath结果：[0, 1, 4, 7, 5, 8, 10, 12, 17]
当前比较行：7，shortTablePath结果：[0, 1, 4, 7, 5, 8, 10, 12, 16]
当前比较行：8，shortTablePath结果：[0, 1, 4, 7, 5, 8, 10, 12, 16]
拓扑排序
2、图的最短路径
public class DnjavaDijstra {
private final static int MAXVEX = 9;
private final static int MAXWEIGHT = 65535;
private int shortTablePath[] = new int[MAXVEX];// 记录的是v0到某顶点的最短路径和
/**
* 获取一个图的最短路径
* 首先在第一行找出一个最小的值（下标1），表示v0到v1(k=1)的最短路径。
* 其次在遍历第k行数据，满足没有被标记并且graph[k][j]+min<shortTablePath[j],表示v0到vj存在更小的路径。
* 重复以上步骤，循环顶点个数减1次。
*/
public void shortestPathDijstra(Graph graph) {
int min;//最小值且没确定是最短路径
int k = 0;// 记录下标
//与shortTablePath对应，表示每个节点最短路径有没有被确定
boolean isgetPath[] = new boolean[MAXVEX];
//获取v0这一行的权值数组
for (int v = 0; v < graph.getVertexSize(); v++) {
shortTablePath[v] = graph.getMatrix()[0][v];//
}
shortTablePath[0] = 0;
isgetPath[0] = true;
System.out.println("当前比较行：0，shortTablePath结果："+Arrays.toString(shortTablePath));
//遍历行，除过第0行（数组）遍历剩余graph.getVertexSize()-1行,不是按照顺序遍历，跟k有关
for (int l = 1; l < graph.getVertexSize(); l++) {
min = MAXWEIGHT;
//在shortTablePath数组中查找最小值，且没有被标记过
for (int w = 0; w < graph.getVertexSize(); w++) {
if (!isgetPath[w] && shortTablePath[w] < min) {
k = w;
min = shortTablePath[w];
}
}
isgetPath[k] = true;
//当前行的每一列j数据与min之和如果小于shortTablePath[j],说明v0到vv
for (int j = 0; j < graph.getVertexSize(); j++) {
if(!isgetPath[j]&&(min+graph.getMatrix()[k][j]<shortTablePath[j])){
shortTablePath[j] = min + graph.getMatrix()[k][j];
}
}
System.out.println("当前比较行："+k+"，shortTablePath结果："
+Arrays.toString(shortTablePath));
}
for(int i = 0;i<shortTablePath.length;i++){
System.out.println("V0到V"+i+"的最短路径为:"+shortTablePath[i]+"\n");
}
}
public static void main(String[] args){
Graph graph = new Graph(MAXVEX);
graph.createGraph();
DnjavaDijstra dijstra = new DnjavaDijstra();
dijstra.shortestPathDijstra(graph);
}
}
3、图的拓扑排序
package com.dn.dijstra;
import java.util.Stack;
public class DnGraphTopologic {
private int numVertexes;
private VertexNode [] adjList;//邻接顶点的一维数组
public DnGraphTopologic(int numVertexes){
this.numVertexes = numVertexes;
}
private void createGraph(){
VertexNode node0 = new VertexNode(0,"v0");
VertexNode node1 = new VertexNode(0,"v1");
VertexNode node2 = new VertexNode(2,"v2");
VertexNode node3 = new VertexNode(0,"v3");
VertexNode node4 = new VertexNode(2,"v4");
VertexNode node5 = new VertexNode(3,"v5");
VertexNode node6 = new VertexNode(1,"v6");
VertexNode node7 = new VertexNode(2,"v7");
VertexNode node8 = new VertexNode(2,"v8");
VertexNode node9 = new VertexNode(1,"v9");
VertexNode node10 = new VertexNode(1,"v10");
VertexNode node11 = new VertexNode(2,"v11");
VertexNode node12 = new VertexNode(1,"v12");
VertexNode node13 = new VertexNode(2,"v13");
adjList = new VertexNode[numVertexes];
adjList[0] =node0;
adjList[1] =node1;
adjList[2] =node2;
adjList[3] =node3;
adjList[4] =node4;
adjList[5] =node5;
adjList[6] =node6;
adjList[7] =node7;
adjList[8] =node8;
adjList[9] =node9;
adjList[10] =node10;
adjList[11] =node11;
adjList[12] =node12;
adjList[13] =node13;
node0.firstEdge = new EdgeNode(11);node0.firstEdge.next = new EdgeNode(5);node0.firstEdge.next.next = new EdgeNode(4);
node1.firstEdge = new EdgeNode(8);node1.firstEdge.next = new EdgeNode(4);node1.firstEdge.next.next = new EdgeNode(2);
node2.firstEdge = new EdgeNode(9);node2.firstEdge.next = new EdgeNode(6);node2.firstEdge.next.next = new EdgeNode(5);
node3.firstEdge = new EdgeNode(13);node3.firstEdge.next = new EdgeNode(2);
node4.firstEdge = new EdgeNode(7);
node5.firstEdge = new EdgeNode(12);node5.firstEdge.next = new EdgeNode(8);
node6.firstEdge = new EdgeNode(5);
node8.firstEdge = new EdgeNode(7);
node9.firstEdge = new EdgeNode(11);node9.firstEdge.next = new EdgeNode(10);
node10.firstEdge = new EdgeNode(13);
node12.firstEdge = new EdgeNode(9);
}
/**
* 拓扑排序
* @author Administrator
* @throws Exception
*
*/
private void topologicalSort() throws Exception{
Stack<Integer> stack = new Stack<>();
int count = 0;
int k = 0;
for(int i = 0;i<numVertexes;i++ ){
if(adjList[i].in == 0){
stack.push(i);
}
}
while(!stack.isEmpty()){
int pop = stack.pop();
System.out.println("顶点："+adjList[pop].data);
count++;
for(EdgeNode node = adjList[pop].firstEdge;node!=null;node = node.next){
k = node.adjVert;//下标
if(--adjList[k].in == 0){
stack.push(k);//入度为0,入栈
}
}
}
if(count<numVertexes){
throw new Exception("完犊子了，拓扑排序失败");
}
}
//边表顶点
class EdgeNode{
private int adjVert;
private EdgeNode next;
private int weight;
public EdgeNode(int adjVert){
this.adjVert = adjVert;
}
public int getAdjVert() {
return adjVert;
}
public void setAdjVert(int adjVert) {
this.adjVert = adjVert;
}
public EdgeNode getNext() {
return next;
}
public void setNext(EdgeNode next) {
this.next = next;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
//邻接顶点
class VertexNode{
private int in;//入度
private String data;
private EdgeNode firstEdge;
public VertexNode(int in,String data){
this.in = in;
this.data = data;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public EdgeNode getFirstEdge() {
return firstEdge;
}
public void setFirstEdge(EdgeNode firstEdge) {
this.firstEdge = firstEdge;
}
}
public static void main(String [] args){
DnGraphTopologic dnGraphTopologic = new DnGraphTopologic(14);
dnGraphTopologic.createGraph();
try {
dnGraphTopologic.topologicalSort();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
网友评论