글 읽기 - 우선순위 큐를 이용한 다익스트라 질문.. (visited 배열)

uglyonlytoday 4년 전 1

우선순위 큐를 이용해 다익스트라를 구현할 때 보통 값 갱신이 일어날 것을 대비해 52번째 줄처럼 거르는 방식을 쓰시던데

저는 인접행렬에서 다익스트라를 구현하는 것 처럼 visited 배열을 사용해 한번 방문한 정점은 방문하지 못하게 막았더니 AC가 떴습니다. 2번 코드처럼 다익스트라를 구현해도 문제가 없는 걸까요.. 혹시 저격 데이터가 있을까요?

#include <stdio.h>
#include <vector>
#include <queue>
#define MAX_VERTEX 20000
#define INF 99999999

using namespace std;

struct Node
{
    int vertex, weight;
    Node(int d, int w) : vertex(d), weight(w) {}
};

bool operator<(Node a, Node b)
{
    return a.weight > b.weight;
}

class WeightGraph
{
protected:
    vector<Node> graph[MAX_VERTEX];

public:
    int size;
    WeightGraph(int s) : size(s) {}

    void addEdge(int a, int b, int w)
    {
        graph[a].push_back(Node(b, w));
    }
};

class DijkstraPath : public WeightGraph
{
public:
    DijkstraPath(int s) : WeightGraph(s) {}
    //1번 코드
    vector<int> getShortestPath(int s)
    {
        vector<int> distance(size, INF);
        distance[s] = 0;
        priority_queue<Node> pq;
        pq.push(Node(s, 0));
        while (!pq.empty())
        {
            Node t = pq.top();
            pq.pop();

            if (distance[t.vertex] < t.weight)
            {
                continue;
            }

            for (auto m : graph[t.vertex])
            {
                if (t.weight + m.weight < distance[m.vertex])
                {
                    distance[m.vertex] = t.weight + m.weight;
                    pq.push(Node(m.vertex, t.weight + m.weight));
                }
            }
        }
        return distance;
    }
};

//2번 코드
vector<int> getShortestPath(int s)
	{
		vector<int> distance(size, INF);
		vector<bool> visited(size, false);
		distance[s] = 0;
		priority_queue<Node> pq;
		pq.push(Node(s, 0));
		while (!pq.empty())
		{
			Node t = pq.top();
			pq.pop();

			if (visited[t.vertex])
			{
				continue;
			}
			visited[t.vertex] = true;

			for (auto m : graph[t.vertex])
			{
				if (!visited[m.vertex] && t.weight + m.weight < distance[m.vertex])
				{
					distance[m.vertex] = t.weight + m.weight;
					pq.push(Node(m.vertex, t.weight + m.weight));
				}
			}
		}
		return distance;
	}

djm03178 4년 전 0

둘 다 같은 효과를 냅니다.

uglyonlytoday 4년 전 0

답변 정말 감사드립니다!!

그럼 혹시 시간 복잡도에서 차이는 있을까요?

djm03178 4년 전 0

같은 효과라는 것은 시간 복잡도를 포함해서 말씀드린 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

우선순위 큐를 이용한 다익스트라 질문.. (visited 배열)

uglyonlytoday 4년 전 1

djm03178 4년 전 0

uglyonlytoday 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말