๊ทธ๋ํ ์ค์์ ์ต๋จ ๊ฒฝ๋ก
๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ค์ ํ๋๋ก ํ๋์ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ (single-source shortest path algorithmm)
์์ ๊ฐ์ค์น๋ ๊ณ์ฐ ํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
Vertex์ ๊ฐ์๊ฐ N๊ฐ์ผ ๋, ํ vertex์์ ๋ค๋ฅธ vertex๊น์ง ๊ฐ๋๋ฐ ๊ฑฐ์น๋ edge์๋ ์ต์ 1๊ฐ๋ถํฐ, ์ต๋ N-1๋ฒ ๊ฑฐ์น๊ฒ ๋ ๊ฒ์ด๋ค.
relax
์ ๊ฐ๋
์ ์ด์ฉํ๋ฉฐ relax๋ ํ์ฌ ๊ณ์ฐ๋ v๋
ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ๋ณด๋ค ํ์ฌ ๋
ธ๋ u๊น์ง์ ๊ฒฝ๋ก์ u์์ v์ ๊ฐ์ค์น ( e(u,v)
) ๊ฐ ๋ ์๋ค๋ฉด ๊ฐ์ ๊ฐฑ์ ํด์ฃผ๋ ๊ฒ.
relax
๋ prim ์๊ณ ๋ฆฌ์ฆ์ decrease-key
์ ์ ์ฌํ๋ฉฐ dp๋ฅผ ์ถ๊ฐํ ๊ฐ๋
ํน์ง
์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ ๊ฒฝ๋ก๋ฅผ ํฌํจํด๋ ๊ตฌํ ์ ์๋ค.
์์ ์ฌ์ดํด ์กด์ฌ ์ฌ๋ถ๋ฅผ ์ ์ ์๋ค. ( ๋ฌดํ ๋ฃจํ )
edge ์ ์ ๋ณด๋ก ์
๋ ฅ์ด ์ฃผ์ด์ง๋ฉด ์ธ์ ํ๋ ฌ, ์ธ์ ๋ฆฌ์คํธ๋ฅผ ์ ๋ง๋ค๊ณ ๋ ๊ตฌํ ์ ์๋ค.
Pesudo Code
Copy BELLMAN-FORD(G, w , s){
INITIALIZE-SINGLE-SOURCE(G, s)
for i = 1 to |G.V| - 1
for each edge (u,v) โ G.E
RELAX (u,v,w)
for each edge (u,v) โ G.E
if v.d > u.d + w(u,v)
return false
return true
}
Copy RELAX(u,v,w)
if v.d > u.d + w(u,v)
v.d = u.d + w(u,v)
v.ฯ = u
๊ตฌํ ๋ฐฉ๋ฒ
vertex๋ค์ key๊ฐ์ Infinity๋ก ์ด๊ธฐํํ๋ค.
start vertex์ key๊ฐ์ 0์ผ๋ก ์ด๊ธฐํํ๋ค.
๋ชจ๋ edge์ ๋ํด relax๋ฅผ ์ํํ๋ค.
3๋ฒ์ V-1๋ฒ ๋ฐ๋ณต ํ๋ค.
4๋ฒ์ด ๋๋๋ฉด ์ต๋จ ๊ฒฝ๋ก๋ ๊ตฌํด์ก์ผ๋ฉฐ, ์์ ์ฌ์ดํด์ด ์๋์ง ์๋์ ๋ฐฉ๋ฒ์ผ๋ก ๊ฒ์ฌํ๋ค.
๋ชจ๋ edge์ ๋ํด ๋ชฉ์ ์ง vertex์ ์ต๋จ ๊ฒฝ๋ก ๊ฐ์ด ์ถ๋ฐ์ง vertex๊น์ง์ ์ต๋จ ๊ฒฝ๋ก ๊ฐ + w(u,v) ๋ณด๋ค ํฐ์ง ๊ฒ์ฌํ๋ค.
๋ง์ฝ ํฌ๋ค๋ฉด ์์ ์ฌ์ดํด์ด ์กด์ฌํ๊ณ ๋ชจ๋ edge์ ๋ํด ์๋๋ผ๋ฉด ์์ ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋ ๊ทธ๋ํ์ด๋ค.
Copy std :: vector < int > vertex_key ( V , INFINITY ); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < V; j ++ ) {
for ( int k = 0 ; k < V; k ++ ) {
if ( vertex_key [k] > adjMatrix [j][k] + vertex_key [j]) {
vertex_key [k] = adjMatrix [j][k] + vertex_key [j];
}
}
}
}
for ( int j = 0 ; j < V; j ++ ) {
for ( int k = 0 ; k < V; k ++ ) {
if ( vertex_key [k] > adjMatrix [j][k] + vertex_key [j]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
}
return vertex_key;
Copy std :: vector < int > vertex_key ( V , INFINITY ); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
int dest , weight;
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < adjList . size (); j ++ ) {
for ( int k = 0 ; k < adjList [j] . size (); k ++ ) {
dest = adjList [j][k] . second;
weight = adjList [j][k] . first;
if ( vertex_key [dest] > weight + vertex_key [j]) {
vertex_key [dest] = weight + vertex_key [j];
}
}
}
}
for ( int j = 0 ; j < adjList . size (); j ++ ) {
for ( int k = 0 ; k < adjList [j] . size (); k ++ ) {
dest = adjList [j][k] . second;
weight = adjList [j][k] . first;
if ( vertex_key [dest] > weight + vertex_key [j]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
}
return vertex_key;
edge ์ ๋ณด๋ก ์ฃผ์ด์ก์ ๊ฒฝ์ฐ
Copy std :: vector < int > vertex_key ( V , INFINITY ); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
int src , dest , weight;
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < g . size (); j ++ ) {
src = g [j] . getSrc ();
dest = g [j] . getDest ();
weight = g [j] . getWeight ();
if ( vertex_key [dest] > weight + vertex_key [src]) {
vertex_key [dest] = weight + vertex_key [src];
}
}
}
for ( int j = 0 ; j < g . size (); j ++ ) {
src = g [j] . getSrc ();
dest = g [j] . getDest ();
weight = g [j] . getWeight ();
if ( vertex_key [dest] > weight + vertex_key [src]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
return vertex_key;
์๊ฐ ๋ณต์ก๋
์ด๊ธฐํํ๋๋ฐ O(|V|) ์ด ์์๋๊ณ , ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋๋ฐ O(|E|)๋ฒ์ relax๊ฐ |V-1|๋ฒ ๋ฐ๋ณตํ๊ธฐ ๋๋ฌธ์, O(|V||E|)๋งํผ์ ์๊ฐ์ด ์์๋๋ค.
(relax๋ ๋น๊ตํ ๋จ์ ๋์
์ด๋ฏ๋ก O(1)์ ์๊ฐ ์์)
์์ ์ฌ์ดํด์ด ์กด์ฌํ๋ ์ง ๊ฒ์ฌํ๋๋ฐ |E\๋ฒ ๋ฐ๋ณตํ๊ธฐ ๋๋ฌธ์, O(|E|)๋งํผ์ ์๊ฐ์ด ์์๋๋ค.
๋ฐ๋ผ์ ์ด O(|V||E|)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๋๋ค.
๊ตฌํ ์ฝ๋
์๋ ์ฝ๋๋ ์ฌ์ดํด์ด์๋ ๋ฐฉํฅ์ ๊ทธ๋ํ์ด๊ณ , ์์ ๊ฐ์ค์น๋ฅผ ๋ฌด์์๋ก ์์ฑํ ๊ทธ๋ํ์ด๋ค.
์์ค์ฝ๋ c++ ( ์ ๊ธฐ / ํผ์น๊ธฐ )
Copy #include <time.h> //์๊ฐ ์ธก์
#include <algorithm> //for_each
#include <cstdlib> //rand
#include <ctime> //time
#include <iostream>
#include <string>
#include <vector>
#define INFINITY 2140000000
#define II std :: pair <int , int> // first = weight, second = dest
typedef struct edge {
int src; //์ถ๋ฐ vertex
int dest; //๋์ฐฉ vertex
int weight; //๊ฐ์ค์น(๋น์ฉ)
} edge ;
class Graph {
private :
edge e;
public :
Graph ( int src = 0 , int dest = 0 , int weight = 0 ) {
this -> e . src = src;
this -> e . dest = dest;
this -> e . weight = weight;
}
int getSrc () { return this -> e . src; }
int getDest () { return this -> e . dest; }
int getWeight () { return this -> e . weight; }
};
void CalcTime ();
void randomPush (std :: vector < Graph > & ); // graph์ ์ฌ์ดํด ์๋ ์ฐ๊ฒฐ๊ทธ๋ํ cost๊ฐ ๋ฌด์์ ์์ฑ
void print_edge_info (std :: vector < Graph >); // graph ๊ฐ์ ๋ค ๋ณด๊ธฐ
void make_adj_list (std :: vector < Graph > , std :: vector <std :: vector < II >> & ); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ๋ฆฌ์คํธ๋ก ํํ
void make_adj_matrix (std :: vector < Graph > , std :: vector <std :: vector < int >> & ); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ํ๋ ค๋ก ํํ
std :: vector < int > bellman_ford_list (std :: vector <std :: vector < II >> , int );
std :: vector < int > bellman_ford_array (std :: vector <std :: vector < int >> , int );
std :: vector < int > bellman_ford_edge (std :: vector < Graph > , int );
int V; // vertex ๊ฐ์
clock_t start , finish , used_time = 0 ; //์คํ ์๊ฐ ์ธก์ ์ ์ํ ๋ณ์
int main () {
std :: vector < Graph > g; // graph g
std :: vector <int> shortestPath;
std :: vector < std :: vector <int>> adjMatrix;
std :: vector < std :: vector < II >> adjList;
randomPush (g); //๊ฐ์ random ์ฝ์
print_edge_info (g); // edge info print
make_adj_matrix (g , adjMatrix); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ํ๋ ฌ๋ก ๋ง๋ค๊ธฐ
make_adj_list (g , adjList); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ๋ฆฌ์คํธ๋ก ๋ง๋ค๊ธฐ
start = clock ();
// shortestPath = bellman_ford_list(adjList, 0); // list์ ์ด์ฉํ ๊ตฌํ
// shortestPath = bellman_ford_array(adjMatrix, 0); // array ์ด์ฉํ ๊ตฌํ
shortestPath = bellman_ford_edge (g , 0 ); // array ์ด์ฉํ ๊ตฌํ
finish = clock ();
for ( int i = 0 ; i < V; i ++ ) {
std::cout << "dest : " << i << " (cost : " << ((shortestPath[i] == INFINITY) ? "no path" : std::to_string(shortestPath[i])) << " )"
<< std :: endl;
}
CalcTime ();
return 0 ;
}
std :: vector < int > bellman_ford_list (std :: vector <std :: vector < II >> adjList , int start) {
std :: vector <int> vertex_key (V , INFINITY); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
int dest , weight;
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < adjList . size (); j ++ ) {
for ( int k = 0 ; k < adjList [j] . size (); k ++ ) {
dest = adjList [j][k] . second;
weight = adjList [j][k] . first;
if ( vertex_key [dest] > weight + vertex_key [j]) {
vertex_key [dest] = weight + vertex_key [j];
}
}
}
}
for ( int j = 0 ; j < adjList . size (); j ++ ) {
for ( int k = 0 ; k < adjList [j] . size (); k ++ ) {
dest = adjList [j][k] . second;
weight = adjList [j][k] . first;
if ( vertex_key [dest] > weight + vertex_key [j]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
}
return vertex_key;
}
std :: vector < int > bellman_ford_array (std :: vector <std :: vector < int >> adjMatrix , int start) {
std :: vector <int> vertex_key (V , INFINITY); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < V; j ++ ) {
for ( int k = 0 ; k < V; k ++ ) {
if ( vertex_key [k] > adjMatrix [j][k] + vertex_key [j]) {
vertex_key [k] = adjMatrix [j][k] + vertex_key [j];
}
}
}
}
for ( int j = 0 ; j < V; j ++ ) {
for ( int k = 0 ; k < V; k ++ ) {
if ( vertex_key [k] > adjMatrix [j][k] + vertex_key [j]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
}
return vertex_key;
}
std :: vector < int > bellman_ford_edge (std :: vector < Graph > g , int start) {
std :: vector <int> vertex_key (V , INFINITY); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
int src , dest , weight;
vertex_key [start] = 0 ;
std :: cout << "\nsrc : " << start << std :: endl;
for ( int i = 0 ; i < V - 1 ; i ++ ) {
for ( int j = 0 ; j < g . size (); j ++ ) {
src = g [j] . getSrc ();
dest = g [j] . getDest ();
weight = g [j] . getWeight ();
if ( vertex_key [dest] > weight + vertex_key [src]) {
vertex_key [dest] = weight + vertex_key [src];
}
}
}
for ( int j = 0 ; j < g . size (); j ++ ) {
src = g [j] . getSrc ();
dest = g [j] . getDest ();
weight = g [j] . getWeight ();
if ( vertex_key [dest] > weight + vertex_key [src]) {
std :: cout << "์์ ์ฌ์ดํด์ ๊ฐ๋ ๊ทธ๋ํ์
๋๋ค." << std :: endl;
exit ( 1 );
}
}
return vertex_key;
}
void make_adj_list (std :: vector < Graph > g , std :: vector <std :: vector < II >> & adj) {
adj . resize (V);
bool isEdge;
for ( int i = 0 ; i < g . size (); i ++ ) {
isEdge = false ;
int src = g [i] . getSrc ();
int dest = g [i] . getDest ();
int weight = g [i] . getWeight ();
/*๋์ผ vertex๋ก ํฅํ๋ ๊ฐ์ ์ค ๊ฐ์ฅ ์์ ๊ฐ๋ง๊ฐ์ง๊ณ ์ธ์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ ์ํ ์ฝ๋*/
if ( adj [src] . empty ()) {
adj [src] . push_back ({weight , dest});
} else {
for ( int j = 0 ; j < adj [src] . size (); j ++ ) {
if ( adj [src][j] . second == dest) {
isEdge = true ;
if ( adj [src][j] . first > weight) {
adj [src][j] . first = weight;
}
}
}
if ( ! isEdge) adj [src] . push_back ({weight , dest});
}
}
}
void make_adj_matrix (std :: vector < Graph > g , std :: vector <std :: vector < int >> & adj) {
adj . assign (V , std :: vector < int >(V , INFINITY));
for ( int i = 0 ; i < g . size (); i ++ ) {
int src = g [i] . getSrc ();
int dest = g [i] . getDest ();
int weight = g [i] . getWeight ();
if ( adj [src][dest] > weight) {
adj [src][dest] = weight;
}
}
}
/*vertex์ ์
๋ ฅ๋ฐ์ ํ ๊ทธ๋ํ ๊ฐ์ ๊ฐ์ค์น random ์ฝ์
*/
void randomPush (std :: vector < Graph > & g) {
std :: cout << "create number of Vertex : " ;
std :: cin >> V;
srand (( unsigned int ) time ( NULL ));
for ( int i = 0 ; i < V - 1 ; i ++ ) {
g . push_back ( Graph (i , i + 1 , rand () % 1000 ));
for ( int j = i + 1 ; j < V; j ++ ) {
g . push_back ( Graph (i , j , rand () % 1000 ));
}
}
for ( int i = ( rand () % 3 ); i < V - 1 ; i += ( rand () % 10 )) {
g . push_back ( Graph (i , i + 1 , rand () % 1000 ));
for ( int j = i + 1 ; j < V; j += ( rand () % 10 )) {
g . push_back ( Graph (i , j , rand () % 1000 ));
}
}
}
void print_edge_info (std :: vector < Graph > g) {
std :: cout << "edge info : \n" ;
std :: for_each ( g . begin () , g . end () , []( Graph a) {
std :: cout << "src : " << a . getSrc () << " desc : " << a . getDest () << " weight : " << a . getWeight () << std :: endl;
});
}
//์คํ ์๊ฐ์ ์ธก์ ๋ฐ ์ถ๋ ฅํ๋ ํจ์
void CalcTime () {
used_time = finish - start;
printf ( "\n*********** result **********\n time : %lf sec\n" , ( double )(used_time) / CLOCKS_PER_SEC);
}