Bellman-Ford 알고리즘 Java 코드

Bellman-Ford

다익스트라 알고리즘 보다 느리지만 음수가 있을 때도 사용 가능

또한 사이클 여부를 확인 할 수 있음

시간복잡도

O(VE)

Java code

public class BellmanFord {
    int vertexNum;
    int edgeNum;
    HashMap<Integer, Double>[] graph; //graph[출발지] = HashMap<도착지, 가중치>
    Double[] distance;
    
    public double bellmanFord(){
        distance[0] = 0.0;
        for(int i=1; i<vertexNum; i++) distance[i] = Double.MAX_VALUE;
        
        boolean update = false;
        for(int i=0; i<vertexNum; i++){
            update = false;
            for(int vi=0; vi<vertexNum; i++){
                for(int adj : graph[vi].keySet()){
                    if(distance[adj] > distance[vi] + graph[vi].get(adj)){
                        distance[adj] = distance[vi] + graph[vi].get(adj);
                        update = true;
                    }
                }
            }
            if(!update) break; //완화를 전부 
        }
        if(update) return Integer.MAX_VALUE; //(VertexNum - 1)번 한 후 완화 가능하면 사이클이 존재하는 것
        return distance[edgeNum - 1];
    }
}