シングルソース最短パス(C++実装)

図の構造

#include 
#include 

using namespace std;

struct edge{
	int to, cost;
};

const int MAX = 1000;

vector G[MAX]; //  
int V; //    
int E; //   

void creat(){
	//          0 ~ n，       1 ~ n,               1    
	//       0 ~ n
	cin >> V >> E;
	for(int i = 0; i < E; ++i){
	    int from, to, cost;
	    cin >> from >> to >> cost;
	    edge e;
	    e.to = to;
	    e.cost = cost;
	    G[from].push_back(e);
	}
}

int main(){
	creat();
	return 0;
}

Dijkstraアルゴリズム(最適化されていない)

#include 
#include 

using namespace std;

struct edge{
	int to, cost;
};

const int MAX = 10001;
const int INF = 0x3f3f3f3f; //              

vector G[MAX]; //  
int d[MAX];
int used[MAX];
int V; //    
int E; //   
int s; //     

void creat(){
	//          0 ~ n，       1 ~ n,               1    
	//       0 ~ n
	cin >> V >> E >> s;
	for(int i = 0; i < E; ++i){
	    int from, to, cost;
	    cin >> from >> to >> cost;
	    edge e;
	    e.to = to;
	    e.cost = cost;
	    G[from].push_back(e);
	}
}

void Dijkstra(int s){
	fill(d, d + V, INF);
	fill(used, used + V, false);
	d[s] = 0;
	while(true){
	    int v = -1;
	    for(int i = 0; i < V; ++i){
		if(!used[i] && (v == -1 || d[v] > d[i])){ //             
			v = i;
		}
	    }
	    if(v == -1) break;
	    used[v] = true;
	    for(int i = 0; i < (int)G[v].size(); ++i){
	        edge e = G[v][i];
		if(d[v] != INF) //             ，     
                d[e.to] = min(d[e.to], d[v] + e.cost); // v -> i  v  e.to     
	    }
	}
}

void solve(){
	creat();
	Dijkstra(s);
	for(int i = 0; i < V; ++i) cout << d[i] << ' '; //              ，           INF
}

int main(){
	solve();
	return 0;
}

Dijkstra(優先キューの最適化)

#include 
#include 
#include 
#include 

using namespace std;

struct edge{
	int to, cost;
};

typedef pair P;
const int MAX = 10001;
const int INF = 0x3f3f3f3f; //               

vector G[MAX]; //  
int d[MAX];
int used[MAX];
int V; //    
int E; //   
int s; //     

void creat(){
	//          0 ~ n，       1 ~ n,               1    
	//       0 ~ n
	cin >> V >> E >> s;
	for(int i = 0; i < E; ++i){
	    int from, to, cost;
	    cin >> from >> to >> cost;
	    edge e;
	    e.to = to;
	    e.cost = cost;
	    G[from].push_back(e);
	}
}

void Dijkstra(int s){
    priority_queue
, greater
 > que; //      
    fill(d, d + V, INF);
    que.push(P(0, s));
    d[s] = 0;

    while(!que.empty()){
        P p = que.top(); que.pop();
        int v = p.second; // first        second          
        if(d[v] < p.first) continue; //     ，            v  
        for(int i = 0; i < (int)G[v].size(); ++i){
            edge e = G[v][i]; // v -> e.to   
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

void solve(){
	creat();
	Dijkstra(s);
	for(int i = 0; i < V; ++i) cout << d[i] << ' '; //              ，           INF
}

int main(){
	solve();
	return 0;
}

SPFA

#include 
#include 
#include 

using namespace std;

struct edge{
	int to, cost;
};

const int MAX = 10001;
const int INF = 0x3f3f3f3f; //               

vector G[MAX]; //  
int visit[MAX]; //      
int d[MAX];
int used[MAX];
int V; //    
int E; //   
int s; //     

void creat(){
	//          0 ~ n，       1 ~ n,               1    
	//       0 ~ n
	cin >> V >> E >> s;
	for(int i = 0; i < E; ++i){
	    int from, to, cost;
	    cin >> from >> to >> cost;
	    edge e;
	    e.to = to;
	    e.cost = cost;
	    G[from].push_back(e);
	}
}

void BFS_Dijkstra(int s){
    queue que;
    fill(d,  d + V, INF);
    que.push(s);
    d[s] = 0;

    while(!que.empty()){
        int v = que.front(); que.pop();
        visit[v] = 0; //       v  ,          
        for(int i = 0; i < (int)G[v].size(); ++i){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                if(!visit[e.to]){
                    visit[e.to] = 1;
                    que.push(e.to);
                }
            }
        }
    }
}

void solve(){
	creat();
	BFS_Dijkstra(s);
	for(int i = 0; i < V; ++i) cout << d[i] << ' '; //              ，           INF
}

int main(){
	solve();
	return 0;
}

Bellman_Fordアルゴリズム

#include 
#include 

using namespace std;

//  
struct edge{
    int from, to, cost;
};

const int INF = 0x3f3f3f3f;
const int V_MAX = 10001; //        
const int E_MAX = 10001; //       
int V; //          0 ~ n
int E; //   
int s; //   
edge es[E_MAX];
int d[V_MAX];

void creat(){ //    ，        
    cin >> V >> E >> s;
    for(int i = 0; i < E; ++i){
        cin >> es[i].from >> es[i].to >> es[i].cost; // from -> to       = cost
    }
}

void Bellman_Ford(int s){
    fill(d, d + V, INF);
    d[s] = 0;

    while(true){
        bool update = false;
        for(int i = 0; i < E; ++i){
            edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){ //       e.to      
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(!update) break; //              ，   ！
    }
}

//       
//                （         V - 1  ，whlie(true)      V - 1 ）
//   ，      s      ，     | V |         d   
 
bool find_negative_loop(){
    memset(d, 0, sizeof(d));

    for(int i = 0; i < V; ++i){
        for(int j = 0; j < E; ++j){
            edge e = es[j];
            if(d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                if(i == V - 1) return false;
            }
        }
    }
    return true;
}

void solve(){
    creat();
    Bellman_Ford(s);
    for(int i = 0; i < V; ++i) cout << d[i] << ' '; //       
}

int main(){
    solve();
    return 0;
}