當前比較行：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存在更小的路徑彤路。
* 重復以上步驟秕硝，循環(huán)頂點個數減1次。
*/
public void shortestPathDijstra(Graph graph) {
int min;//最小值且沒確定是最短路徑
int k = 0;// 記錄下標
//與shortTablePath對應洲尊，表示每個節(jié)點最短路徑有沒有被確定
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();
}
}
}
