020 무 환 가중 권 은 그림 의 최 단 경로 로 이 루어 집 니 다.

무 환 가중 권 은 그림 의 최 단 경로 로 이 루어 집 니 다.

그림 학습 노트 색인

본 고 는

을 참고 한다.

1. 의존 류

2. 무 환 가중 방향 그림 의 최 단 경로

그림 학습 노트 색인
001 사용자 정의 입력 흐름 In 클래스 구현 002 가방 데이터 형식 Bag 구현 003 무 방향 그림 데이터 형식 실현 004 그림 기반 깊이 우선 검색 005 사용 깊이 우선 검색 그림 의 모든 연결 분량 005 - 1 깊이 우선 검색 그림 에서 연결 경로 006 기반 깊이 우선 검색 판단 그림 에 링 007 기반 깊이 우선 검색 판단 그림 에 존재 하 는 지 여 부 를 기반 으로 무 방향 그림 을 판단 합 니 다.2 분 그림 008 너비 우선 검색 연결 그림 에서 가장 짧 은 경로 009 방향 그림 데이터 형식 으로 010 방향 그림 의 접근 성 011 가중치 가 있 는 무 방향 데이터 형식 Edge 실현 012 가중 무 방향 그림 데이터 형식 실현 013 방향 링 014 방향 그림 에서 깊이 우선 검색 을 바탕 으로 하 는 정점 정렬 015 검색, 정렬, 기호 표,산 목록 등 알고리즘 구현 (1) 016 최소 생 성 트 리 Prim 알고리즘 지연 실현 017 최소 생 성 트 리 Prim 알고리즘 즉시 구현 018 가중 방향 및 가중 방향 그림 의 실현 019 방향 그림 의 최 단 경로 Dijkstra 알고리즘 구현
본 고 는 을 참고 한다.
1. 의존 류
파일 에서 그림 의 정점 관 계 를 읽 습 니 다.tinyEWDAG. txt 내용: 8 13 5 4 0.35 4 7 0.37 5 1 0.32 4 0 0.38 0 2 0.26 3 7 0.39 1 3 0.29 7 0.34 6 2 0.40 3 6 0.52 6 6 4 0.93
텍스트 가 져 오기 클릭: 001 사용자 정의 입력 흐름 클래스 구현
2. 무 환 가중 권 은 그림 의 가장 짧 은 경로 가 있다.
그림 에 링 코드 가 있 는 지 판단 하기:

package algorithms.graph; 
import java.io.IOException; 
import java.util.Deque;
import java.util.LinkedList; 
/*
 *      ;      
 * */
public class EdgeWeightDirectedCycle {
    private boolean marked[];
    private int edgeTo[];
    private Deque<Integer> cycle;
    private boolean onStack[];
    public EdgeWeightDirectedCycle(EdgeWeightedDigraph D){
    	marked = new boolean[D.V()];
    	edgeTo = new int[D.V()];
    	onStack = new boolean[D.V()];
    	for(int s = 0; s < D.V(); s++)
    		if(!marked[s])
    		   dfs(D, s);
    }
    public void dfs(EdgeWeightedDigraph D, int v){
    	onStack[v] = true;
    	marked[v] = true; 
    	for(DirectedEdge e : D.adj(v)) {
    		int w = e.to();
    		if(this.hasCycle()) return;
    		else if(!marked[w]){
    			edgeTo[w] = v;
    			dfs(D, w);
    		} 
    		else if(onStack[w]){
    			cycle = new LinkedList<Integer>();
    			for(int x = v; x != w; x = edgeTo[x]) 
    				cycle.push(x); 
    			cycle.push(w);
    			cycle.push(v); 
    		}
    	}
    	onStack[v] = false; //           onStack[v] = false
    }
    public boolean hasCycle(){
    	return cycle != null;
    }
    public Iterable<Integer> getCycle(){
		return cycle; 
    }
    public boolean getOnStack(int v){
    	return this.onStack[v];
    }
	public static void main(String[] args) throws IOException {
		In in = new In("D:\\tinyEWD.txt"); 
		EdgeWeightedDigraph D = new EdgeWeightedDigraph(in);
		System.out.println(D); 
		EdgeWeightDirectedCycle dCycle = new EdgeWeightDirectedCycle(D);
		System.out.println(dCycle.hasCycle());
		for(int v : dCycle.getCycle())
			System.out.print(v+"-");
		System.out.println();
		for(int v = 0; v < D.V(); v++)
			System.out.println(v + ": "+ dCycle.getOnStack(v));
	}
}

링 가중 없 는 그림 의 최 단 경로 자바 구현 코드:

package algorithms.graph;
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Deque;
import java.util.LinkedList;
/*
 *             
 */
public class AcyclicSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private Deque reversePost;
    private boolean[] marked;
    public AcyclicSP(EdgeWeightedDigraph G, int s){
    	edgeTo = new DirectedEdge[G.V()];
    	distTo = new double[G.V()];
    	reversePost = new LinkedList();
    	marked = new boolean[G.V()];
    	for(int v = 0; v < G.V(); v++) 
    		distTo[v] = Double.POSITIVE_INFINITY; 
    	distTo[s] = 0.00;
    	EdgeWeightDirectedCycle dcycle = new EdgeWeightDirectedCycle(G);
    	System.out.println(dcycle.hasCycle());
    	if(!dcycle.hasCycle()){
    		for(int v = 0; v < G.V(); v++) 
	    		if(!marked[v])
	    			dfs(G, v); 
    		for(int v : reversePost)
        	    relax(G, v);
    	} 
    }
    private void dfs(EdgeWeightedDigraph G, int v){
    	marked[v] = true;
    	for(DirectedEdge e : G.adj(v)){
    		int w = e.to();
    		if(!marked[w])
    			dfs(G, w);
    	}
    	reversePost.push(v);
    }
    private void relax(EdgeWeightedDigraph G, int v){
    	for(DirectedEdge e : G.adj(v)){
    		int w = e.to();
    		if(distTo[v] + e.weight() < distTo[w]){
    			 distTo[w] = distTo[v] + e.weight();
    			 edgeTo[w] = e;
    		}
    	}
    }
    public double distTo(int v){
    	BigDecimal bd = new BigDecimal(distTo[v]);
    	double d = bd.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
    	return d;
    }
    public Iterable pathTo(int v){
    	Deque dq = new LinkedList();
    	for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
    		dq.push(e);
    	return dq;
    }
    public boolean hasPathTo(int v){
    	return distTo[v] != Double.POSITIVE_INFINITY;
    }
	public static void main(String[] args) throws IOException {
		In in = new In("D:\\tinyEWDAG.txt"); 
		 System.out.println("   ：");
		 for(String v : in.getStr())
				System.out.print(v + " "); 
		 System.out.println();
		 System.out.println("    ：");
		 EdgeWeightedDigraph EWD = new EdgeWeightedDigraph(in);
		 System.out.println(EWD); 
		 AcyclicSP sp = new AcyclicSP(EWD, 5);
		 System.out.println("            ："); 
		 for(int v = 0; v < EWD.V(); v++){
			 System.out.print("5  " + v + "     : "); 
			 for(DirectedEdge e : sp.pathTo(v))
				 System.out.print(e + " ");
			 System.out.println("     " + sp.distTo(v));
		 } 

	}

}

출력:

   ：
8 13 5 4 0.35 4 7 0.37 5 7 0.28 5 1 0.32 4 0 0.38 0 2 0.26 3 7 0.39 1 3 0.29 7 2 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 
    ：
0 : 0-2 0.26  
1 : 1-3 0.29  
2 : 
3 : 3-6 0.52  3-7 0.39  
4 : 4-0 0.38  4-7 0.37  
5 : 5-1 0.32  5-7 0.28  5-4 0.35  
6 : 6-4 0.93  6-0 0.58  6-2 0.40  
7 : 7-2 0.34  

false
            ：
5  0     : 5-4 0.35 4-0 0.38      0.73
5  1     : 5-1 0.32      0.32
5  2     : 5-7 0.28 7-2 0.34      0.62
5  3     : 5-1 0.32 1-3 0.29      0.61
5  4     : 5-4 0.35      0.35
5  5     :      0.0
5  6     : 5-1 0.32 1-3 0.29 3-6 0.52      1.13
5  7     : 5-7 0.28      0.28