다익스트라

다익스트라

참고사이트: [https://hsp1116.tistory.com/42]

배열을 이용한 다익스트라(JAVA)

class Graph{
    boolean[] visited;
    int[] dist;
    int[][] vertex;
    int N;

    public Graph(int N){
        this.N = N;
        visited = new boolean[N];
        dist = new int[N];
        vertex = new int[N][N];

        for(int i = 0; i < dist.length; i++)
            dist[i] = Integer.MAX_VALUE;
    }

    public void setStartVertex(int index){
        visited[index] = true; // 시작 정점 지정
        dist[index] = 0;
    }

    public void inputVertexs(int[][] road){
        int u, v;
        for(int i = 0; i < road.length; i++){ // 입력값 저장
            u = road[i][0] - 1;
            v = road[i][1] - 1;
            if(vertex[u][v] != 0){ // 같은 연결의 새로운 입력이 들어올시 거리가 더 짧은 것을 저장
                if(vertex[u][v] > road[i][2]){
                    vertex[u][v] = road[i][2];
                    vertex[v][u] = road[i][2];
                }
            }
            else{
                vertex[u][v] = road[i][2];
                vertex[v][u] = road[i][2];
            }
        }
    }

    public int[] dijkstra(){
        for(int i = 0; i < N - 1; i++){
            int minValue = Integer.MAX_VALUE;
            int minIndex = 0;

            for(int p = 0; p < N; p++){ // 방문 안한 노드 중 최소값 찾기
                if(!visited[p]){
                    if(dist[p] < minValue){
                        minIndex = p;
                        minValue = dist[p];
                    }
                }
            }

            visited[minIndex] = true;

            for(int p = 0; p < N; p++){ // 인점 정점 중 가장 짧은 경로 찾기
                if(vertex[minIndex][p] != 0){
                    if(dist[p] > dist[minIndex] + vertex[minIndex][p])
                        dist[p] = dist[minIndex] + vertex[minIndex][p];
                }
            }
        }

        return dist;
    }
}

우선순위 큐를 이용한 다익스트라(JAVA)

import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {

        Graph graph = new Graph(6);

        graph.inputVertex(1, 2, 1);
        graph.inputVertex(1, 3, 2);
        graph.inputVertex(2, 3, 2);
        graph.inputVertex(3, 4, 3);
        graph.inputVertex(3, 5, 2);
        graph.inputVertex(3, 5, 3);
        graph.inputVertex(5, 6, 1);

        int[] dist = graph.dijkstra(1);
        System.out.println(dist);
    }
}

class Adjacent implements Comparable<Adjacent>{
    public int index;
    public int weight;

    public Adjacent(int index, int weight){
        this.index = index;
        this.weight = weight;
    }

    public int compareTo(Adjacent target){
        return this.weight > target.weight ? 1 : - 1;
    }
}

class Graph{
    private int[] dist;
    private int N;
    private ArrayList<Adjacent>[] adjs;
    private PriorityQueue<Adjacent> priorityQueue;

    public Graph(int N){
        this.N = N;
        dist = new int[N];
        adjs = new ArrayList[N];
        priorityQueue = new PriorityQueue<>();

        for(int i = 0; i < dist.length; i++)
            dist[i] = Integer.MAX_VALUE;
    }

    public void inputVertex(int index, int to, int weight){
        if(adjs[index - 1] == null)
            adjs[index - 1] = new ArrayList<>();
        adjs[index - 1].add(new Adjacent(to - 1, weight));
        if(adjs[to - 1] == null)
            adjs[to - 1] = new ArrayList<>();
        adjs[to - 1].add(new Adjacent(index - 1, weight));
    }

    public int[] dijkstra(int start){
        dist[start - 1] = 0;
        priorityQueue.offer(new Adjacent(start - 1, 0));

        while(!priorityQueue.isEmpty()){
            int cost = priorityQueue.peek().weight;
            int index = priorityQueue.peek().index;
            priorityQueue.poll();

            if(dist[index] < cost) // 방문할 정점의 비용이 현재 찾은 경로보다 크다면 방문하지 않음
                continue;

            for(int i = 0; i < adjs[index].size(); i++){ // 인접 정점 중 현재 찾은 경로보다 짧은 경로 찾기
                int targetIndex = adjs[index].get(i).index;
                int targetDist = cost + adjs[index].get(i).weight;

                if(dist[targetIndex] > targetDist){
                    dist[targetIndex] = targetDist;
                    priorityQueue.offer(new Adjacent(targetIndex, targetDist));
                }
            }
        }

        return dist;
    }
}

우선순위 큐를 이용한 다익스트라(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

class Graph{
private:
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> priorityQueue;
	std::vector<std::vector<std::pair<int, int>>> adj; // pair에는 가중치, 연결된 정점 번호 순으로 저장
	std::vector<int> dist;
	int N;
	const int maxValue = 2100000000;

public:
	Graph(int n){
		this->N = n;
		dist.resize(n, maxValue);
		adj.resize(n);
	}

	void inputVertex(int index, int to, int weight);
	std::vector<int> dijkstra(int start);
};

void Graph::inputVertex(int index, int to, int weight){
	adj[index - 1].push_back(std::make_pair(weight, to - 1));
	adj[to - 1].push_back(std::make_pair(weight, index - 1));
}

std::vector<int> Graph::dijkstra(int start){
	dist[start - 1] = 0; // 출발지점은 거리가 0

	priorityQueue.push(std::make_pair(0, start - 1));

	while(!priorityQueue.empty()){
		int cost = priorityQueue.top().first;
		int index = priorityQueue.top().second;
		priorityQueue.pop();

		if (dist[index] < cost) // 방문할 정점의 비용이 현재 찾은 경로보다 크다면 방문하지 않음
			continue;

		for(int i = 0; i < adj[index].size(); i++){ // 인접 정점 중 현재 찾은 경로보다 짧은 경로 찾기
			int targetIndex = adj[index][i].second;
			int targetDist = cost + adj[index][i].first;

			if(dist[targetIndex] > targetDist){
				dist[targetIndex] = targetDist;
				priorityQueue.push(std::make_pair(targetIndex, targetDist));
			}
		}
	}

	return dist;
}

int main(){
	Graph graph(6);

	graph.inputVertex(1, 2, 1);
	graph.inputVertex(1, 3, 2);
	graph.inputVertex(2, 3, 2);
	graph.inputVertex(3, 4, 3);
	graph.inputVertex(3, 5, 2);
	graph.inputVertex(3, 5, 3);
	graph.inputVertex(5, 6, 1);

	std::vector<int> dist = graph.dijkstra(1);

	for(auto& itr : dist){
		std::cout << itr << std::endl;
	}

	return 0;
}