プログラミング上達したい人が書くブログ

プログラミング上達したい人が書くブログ

主に、アニメやPython、C++、競技プログラミング(初心者)について書きたいです。また、1週間に一つの記事を心掛けています。学生です。備忘録と書かれたものは他人に見せることを考えて書いてないため見にくいです。

競技プログラミング 備忘録 ダイクストラ編

はじめに

 制限時間内に問題を解く競技プログラミングにおいて、アルゴリズムを調べるために本を読み文字を打ち込むことはとてもめんどくさいと感じたため、ここにMain関数で呼び出して使える形で残しておくことでAtCoderでやるときにコピペで使えるようにしています。

 今回は、有向グラフについて書いてあるが、無向グラフのときは入力のfromとtoのところには逆向きの分もコストを入れている。

 

 最後の表示は、始点firstからそれぞれの最短距離を表示させるコードである。

ダイクストラ法特徴

重みが非負で、閉路が存在しないときに使える。あった場合はベルマンフォード法。

以下の1,2の条の下で進めていく。

1. まだ使われていない頂点の中で d [i] が最小の頂点を探す
2. その頂点に隣接する頂点をさきほどの式を適用して更新する。
ここでつかった頂点はもう使わない。

https://www.npca.jp/works/magazine/2014_1/より引用

O(E*logV)

基本ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MV 100000
#define INF 1e9

struct edge{int to,cost; };
vector <edge> G[MV];
bool used[MV];
int d[MV+1];

int V,E;

void dijkstra(int first){
  fill(d,d+MV,INF);
  fill(used,used+MV,false);
  d[first] = 0;

  for(int i = 0;i < V;i++){
    int now = MV;

    for(int j = 0;j < V;j++){
      if(used[j] == false && d[now] > d[j]){
	now = j;
      }
    }
    // cout << now << endl; デバッグ用、条件1が正しく動作しているかを確かめられる
    used[now] = true;
    for(int j = 0;j < G[now].size();j++){
      edge e = G[now][j];
      d[e.to] = min(d[e.to] , d[now]+e.cost);
    }
    /*for(int j = 0;j < V;j++)
      cout << d[j] << "   ";
      cout << endl; 
デバッグ用で、各点の更新後の最短経路が見れる
*/ } } int main(){ d[MV] = INF+10; int first; cin >> V >> E >> first; for(int i = 0;i < E;i++){ int f,t; edge e; cin >> f >> e.to >> e.cost; G[f].push_back(e); t = e.to; /*e.to = f; G[t].push_back(e);*/ } dijkstra(first); for(int i = 0;i < V;i++){ if(d[i] == INF){ cout << "INF" << endl; } else{ cout << d[i] << endl; } } }

 

各頂点間の最短のコストと求めるソースコード

 すべての頂点間についての最短経路のコストについて求めている。ソースコードは以下のようになる。

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
#define MV 200
#define INF 1e10
 
struct edge{int to,cost; };
vector <edge> G[MV];
 
int V,E;
long long d[MV+1];
 
bool bellmanford(int s){
  fill(d,d+MV,INF);
  d[s] = 0;
  int c = 0;
  bool upd = false;
  while(true){
    upd = false;
    for(int i = 0;i < V;i++){
      for(int j = 0;j < G[i].size();j++){
    edge e = G[i][j];
    if(d[i] != INF && d[e.to] > d[i] + e.cost){
      d[e.to] = d[i] + e.cost;
      upd = true;
    }
      }
    }
    if(!upd)
      break;
    if(c == V-1)
      return true;
    c++;
  }
  return false;
}
 
int main(){
  d[MV] = INF+10;
  int first;
  bool flag;
  cin >> V >> E;
  for(int i = 0;i < E;i++){
    int f,t;
    edge e;
    cin >> f >> e.to >> e.cost;
    G[f].push_back(e);
   
    t = e.to;
    /*
    e.to = f;
    G[t].push_back(e);
    */
  }
  long long vec[V][V];
   
  for(int i = 0;i<V;i++){
    flag = bellmanford(i);
    for(int j = 0;j < V;j++){
      vec[i][j] = d[j];
    }
    if(flag == true)
      break;
  }
  if(flag == true)
    cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0;i < V;i++){
      for(int j = 0;j < V;j++){
    if(vec[i][j] == INF){
      if(j != V-1)
        cout << "INF" << " ";
      else
        cout << "INF";
    }
    else{
      if(j != V-1)
        cout << vec[i][j] << " ";
      else
        cout << vec[i][j];
    }
      }
      cout << endl;
    }
   
  }
   
}