다 익스트라 알고리즘 질문입니다

#include <stdio.h>
#include <stdlib.h>

#define N 6
#define INF 9999

int flag[N + 1];
int dist[N + 1];

int i, j, min, position;

int data[N + 1][N + 1] = {
	{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}
};


void main()
{
	for (i = 1; i <= N; i++) {
		flag[i] = 0;
		dist[i] = INF;
	}

	dist[1] = 0;

	for (i = 1; i <= N; i++) {
		min = INF;
		for (j = 1; j <= N; j++) {
			if (min > dist[i] && flag[j] == 0) {
				min = dist[i] + data[i][j];
				position = j;
			}
		}
		flag[position] = 1;

		for (j = 1; j <= N; j++) {
			if (dist[j] > data[position][j] + dist[position] && data[position][j] != INF) {
				dist[j] = data[position][j] + dist[position];
			}
		}
	}

	for (i = 1; i <= N; i++) {
		printf("1 ~ %d : %d \n", i, dist[i]);
	}
}

이렇게하니 값이
1~1 : 0
1~2 : 2이런식으로 나오기는하는데
혹시 과정까지나오게
1 ~1 : 0 Path : 1
1 ~ 2 : 2 Path : 1 2
1 ~ 3 : 5 Path : 1 4 3 이런식으로 가는 과정나오게 코드 수정할수있는 방법이 없을까요?

음 아쉽지만 위 코드는 다익스트라가 아니에요.

위 예제가 priority_queue를 이용한 방식인데 초보분이 이해하시기에 괜찮은 방법이니 참고해 보세요.
기본적으로 priority_queue도 직접 한번 짜보시길 권해드립니다.

경로를 알고 싶은거라면 min cost를 저장할 때, node의 번호를 최신화 하는 놓는 식으로 path를 찾을 수 있답니다.

min 값을 저장할때 node번호를 최신화하는식이 어떤 느낌일까요 아예 감이 오지않아서… 죄송합니다 ㅠ

간만에 다익스트라 짜봤는데 조금 오래걸렸네요.
여기에 queue를 priority_queue로 바꾸면 다익스트라 자체의 성능과 코드의 가독성 모두 개선 할 수 있습니다.
is_in_queue가 없어도 결과는 나오는 코드지만 priority_queue보다는 덜 하지만 약간의 성능개선을 기대하며 넣은 부분이구요.

이 외에도 여러가지 코드 개선점이 보이지만… 저는 그냥 두겠습니다:wink:

올리신 코드는 플로이드 와셜에 가까워 보이는데 N이 작음에도 반복 수가 적어서 정답도 다르게 나오더라구요.
사실 말씀드리지 말까 했었는데… 착각이 성장에 걸림돌이 되실까 주의하는 차원에서 말씀드립니다.
차근차근 하셔요. 그래야 남아요. :slight_smile:

CODE

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

#define N 6
#define INF 9999

struct Node {
  int before;
  int dist;
  std::vector<int> dests;
};


int cost[N + 1][N + 1] = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}
};

Node nodes[N + 1];
std::queue<int> queue;
bool is_in_queue[N + 1] = { false };

int main(int argc, char** argv)
{
  for (int i = 1; i <= N; i++) {
    nodes[i].before = -1;
    nodes[i].dist = INF;

    for (int des = 1; des <= N; des++) 
      if(cost[i][des] != INF) nodes[i].dests.push_back(des);
    
    queue.push(i);
    is_in_queue[i] = true;
  }

  nodes[1].dist = 0;
  while(!queue.empty()) {
    int now = queue.front();
    queue.pop();
    is_in_queue[now] = false;
    for(auto des : nodes[now].dests) {
      if(nodes[now].dist + cost[now][des] < nodes[des].dist) {
        nodes[des].dist = nodes[now].dist + cost[now][des];
        nodes[des].before = now;
        if(is_in_queue[des] == false) {
          queue.push(des);
          is_in_queue[des] = true;
        }
      }
    }
  }

  nodes[1].before = -1;
  for (int des = 1; des <= N; des++) {
    std::cout << "path " << des;
    int before = nodes[des].before;
    while(before != -1) {
      std::cout << " <- " << before;
      before = nodes[before].before;
    }
    std::cout << " , distance: " << nodes[des].dist << std::endl;
  }
  return 0;
}

RESULT

path 1 , distance: 0
path 2 <- 1 , distance: 2
path 3 <- 4 <- 1 , distance: 5
path 4 <- 1 , distance: 3
path 5 <- 4 <- 1 , distance: 4
path 6 <- 3 <- 4 <- 1 , distance: 8
1 Like

이건 다익스트라 맞는 것 같은데요? 플로이드는 경유-출발-도착의 3중 for문을 사용해 모든 노드 사이의 최단경로를 구하는 알고리즘입니다.


  • 코드 리뷰

스택 크기 초과를 우려해 전역 변수로 선언한 것이라면, 힙에 할당하는 동적 배열(ex. std::vector)을 지역 변수로 사용해 주세요.

함수 간에 공유할 필요가 없는 정보(특히 루프용 변수)는 전역 변수로 선언하지 마세요.

데이터는 별도의 파일로 코드와 분리하는 것이 좋습니다.

for(int i = 0; i < N; ++i)처럼, 루프용 변수를 따로 선언하시고, i++대신 ++i를 사용하시고, 배열의 0번째부터 사용하는 데 익숙해지세요.


경로를 출력하기 위해서는

이 부분에서 '어느 정점을 거쳐왔는가’에 대한 정보를 포함시켜야 합니다.


수정된 코드는 다음과 같습니다(우선순위 큐를 사용한 시간복잡도 개선 없이, 처음 작성하신 코드의 흐름을 그대로 가져왔습니다).

input.txt (없는 길은 0으로 표시)

6
0 2 0 3 0 0
0 0 4 1 7 0
0 0 0 4 1 3
0 2 2 0 1 0
0 0 1 0 0 6
0 3 0 8 0 0

소스코드

#include <iostream>
#include <vector>

constexpr int MAX = 987654321;

auto main() -> int {
    freopen("input.txt", "r", stdin);

    int N; scanf("%d", &N);
    std::vector data(N, std::vector(N, 0));
    std::vector dist(N, MAX), from(N, -1), visited(N, 0);

    for(auto& i: data)
        for(auto& j: i)
            scanf("%d", &j);

    dist[ 0 ] = 0;

    for(; ; ) {
        int mv = MAX, mi = -1;

        for(int i = 0; i < N; ++i)
            if(!visited[ i ] && dist[ i ] < mv)
                mi = i, mv = dist[ i ];

        if(mi == -1) break;
        visited[ mi ] = 1;

        for(int i = 0; i < N; ++i)
            if(data[ mi ][ i ] && dist[ i ] > dist[ mi ] + data[ mi ][ i ])
                dist[ i ] = dist[ mi ] + data[ mi ][ i ],
                from[ i ] = mi;
    }

    for(int i = 0; i < N; ++i) {
        if(!visited[ i ]) continue;
        std::vector< int > path;

        for(int j = i; j; j = from[ j ])
            path.push_back(j);

        printf("[0 -> %d]\n", i);
        printf("dist: %d\n", dist[ i ]);
        printf("path: 0 ");

        for(auto j = path.rbegin(); j != path.rend(); ++j)
            printf("%d ", *j);

        printf("\n\n");
    }

    return 0;
}

결과

[0 -> 0]
dist: 0
path: 0 

[0 -> 1]
dist: 2
path: 0 1 

[0 -> 2]
dist: 5
path: 0 3 2 

[0 -> 3]
dist: 3
path: 0 3 

[0 -> 4]
dist: 4
path: 0 3 4 

[0 -> 5]
dist: 8
path: 0 3 2 5 
1 Like

하 오랜만에 앨거리뜸 하니까 머리가 핑핑 도네요…

앨거리뜸은 역시 몸에 안좋아요.

역시 보털님 제대로 배우신분 :slight_smile:
저는

for
  for
  for

이 구조에서 플로이드로 느꼈어요 ㅋㅋ

for
  for
  for
  for
  for
  for
  for

전 이렇게 보이더군요. ㅎㅎ

보털님이 첫번째 for를 조작하셔서 다익스트라 만드신게 핵심인거 같은데 왜 그건 피드백 안해주셨죠?ㅁ?

금요일밤에 킹고리즘은 해로워요.

1 Like

갈 수 없는 경우의 처리와 경로 저장 이외에는 별로 손볼 곳이 없었습니다.


추가로,

저도 잠시 유혹에 빠졌으나… :thinking:

뭔가 이해가될듯말듯 아리송하네용…

사실 제가말그대로 뉴비라 std::vector라던지 이런거는 아예몰라서… 공부를 더열심히 해야겠네요 ㅠ