minheap, maxheap 복습 및 Priority queue, 다익스트라 알고리즘, 플로이드 워셜 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr;

void push(int num)
{
    arr.push_back(num);
    int now = arr.size() - 1;
    while(now > 1)
    {
        int parent = now / 2;
        if(arr[now] < arr[parent])
        {
            swap(arr[now], arr[parent]);
            now = parent;
        }
        else
            break;
    }
}

void pop()
{
    int now = 1, size = arr.size()-1;
    cout << arr[now] << ' ';
    arr[now] = arr[size--];
    arr.pop_back();
    while(1)
    {
        int child = now * 2;
        if(child > size)
            return;
        
        if(child+1 <= size && arr[child] > arr[child+1]) // 고려해야할 점 오른쪽 자식이 없으면 어떻게 할 것인가?
            child++;
        
        if(arr[now] > arr[child])
        {
            swap(arr[now], arr[child]);
            now = child;
        }
        else
        {
            return;
        }
    }
    
}
int main()
{
    int n;
    cin >> n;
    arr.push_back(0);
    for(int i=0; i<n; i++)
    {
        int num;
        cin >> num;
        push(num);
    }
    pop();
    pop();
    pop();
    pop();
    pop();
    int debug = 1;
    return 0;
}

priority_queue를 사용해서 다익스트라의 최단 거리가 가장 짧은 노드를 찾는데 드는 선형 탐색의 시간을 줄여줌

따라서 위의 선형탐색을 통한 다익스트라보다 개선된 다익스트라 알고리즘이다.

 

코드에 중복되는 부분이 많은데 변수 하나로 값을 저장하여 하면 더 깔끔하게 작성할 수 있을 것 같다.

// 다익스트라 알고리즘 중요한 점
// 지금까지 선형탐색으로 찾았다면 이제 우선순위 큐로 그냥 맨위의 값 뽑아내기
// 그 전에 먼저 다익스트라 알고리즘 구현하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int table[100000];
vector<pair<int, int>> que[100000];
priority_queue<pair<int, int>> q;

void solve(int start)
{
  while(!q.empty())
  {
      int shortest = q.top().first;
      q.pop();
      for(int i=0; i<que[shortest].size(); i++)
      {
          int price = que[shortest][i].second + table[shortest];
          if(price < table[que[shortest][i].first])
          {
              table[que[shortest][i].first] = price;
              q.push({que[shortest][i].first, table[que[shortest][i].first]});
          }
          
      }
  }
    
}
int main()
{
    int n, m, start, end, cost, begin;
    cin >> n >> m >> start;
    for(int i=0; i<11; i++)
    {
        cin >> begin >> end >> cost;
        que[begin].push_back({end, cost});
    }
    fill(table, table + 100000, 21e8);
    table[start] = 0;
    q.push({start, table[start]});
    solve(start);
    for(int i=1; i<=n; i++)
    {
        cout << table[i] << '\n';
    }
    return 0;
}

 

모범 답안을 통해 수정

1. 이미 기록된 경로보다 길다면 넘어간다

2. 힙의 경우 top()에서 작은 값이 나오도록 해야 하므로 

// 다익스트라 알고리즘 중요한 점
// 지금까지 선형탐색으로 찾았다면 이제 우선순위 큐로 그냥 맨위의 값 뽑아내기
// 그 전에 먼저 다익스트라 알고리즘 구현하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int table[100000];
vector<pair<int, int>> que[100000];
priority_queue<pair<int, int>> q;

void solve(int start)
{
  while(!q.empty())
  {
      int shortest = q.top().first;
      int dist = -q.top().second;
      q.pop();
      if(table[shortest] < dist) continue;
      
      for(int i=0; i<que[shortest].size(); i++)
      {
          int price = que[shortest][i].second + table[shortest];
          if(price < table[que[shortest][i].first])
          {
              table[que[shortest][i].first] = price;
              q.push({que[shortest][i].first, -table[que[shortest][i].first]});
          }
          
      }
  }
    
}
int main()
{
    int n, m, start, end, cost, begin;
    cin >> n >> m >> start;
    for(int i=0; i<11; i++)
    {
        cin >> begin >> end >> cost;
        que[begin].push_back({end, cost});
    }
    fill(table, table + 100000, 21e8);
    table[start] = 0;
    q.push({start, -table[start]});
    solve(start);
    for(int i=1; i<=n; i++)
    {
        cout << table[i] << '\n';
    }
    return 0;
}

 

플로이드 워셜 알고리즘

#include <iostream>
#include <algorithm>
using namespace std;
int arr[501][501];
int main()
{
    int num, node, begin, end, cost;
    cin >> num >> node;
    for(int i=0; i<501; i++)
        fill(arr[i], arr[i] + 501, 1e9);
    
    
    for(int i=0; i<node; i++)
    {
        cin >> begin >> end >> cost;
        arr[begin-1][end-1] = cost;
    }
    
    for(int i=0; i<num; i++)
    {
        for(int j=0; j<num; j++)
        {
            if(j == i) continue;
            for(int k=0; k<num; k++)
            {
                if(k == i) continue;
                if(j == k)
                {
                    arr[j][k] = 0;
                    continue;
                }
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
    
    for(int i=0; i<num; i++)
    {
        for(int j=0; j<num; j++)
        {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

음수인 간선이 존재할 수 있으므로 23번 줄, 26번 줄은 삭제해주었다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[501][501];
int main()
{
    int num, node, begin, end, cost;
    cin >> num >> node;
    for(int i=0; i<501; i++)
        fill(arr[i], arr[i] + 501, 1e9);
    
    
    for(int i=0; i<node; i++)
    {
        cin >> begin >> end >> cost;
        arr[begin-1][end-1] = cost;
    }
    
    for(int i=0; i<num; i++)
    {
        for(int j=0; j<num; j++)
        {
            for(int k=0; k<num; k++)
            {
                if(j == k)
                {
                    arr[j][k] = 0;
                    continue;
                }
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
    
    for(int i=0; i<num; i++)
    {
        for(int j=0; j<num; j++)
        {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}