Bellman-Ford Dijkstra SPFA
3つの最短パスアルゴリズム
Dijkstra:
Bellman-Ford:
SPFA:
Dijkstra:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=-1;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int node;
int weight;
int parent;
}STORE;
bool operator< (const STORE& lhs, const STORE& rhs){
if(lhs.weight > rhs.weight)
return true;
else
return false;
}
bool FIND_STORE(const vector<STORE>& S,const STORE TMP){
for(int i=0;i<S.size();i++)
if(S[i].node == TMP.node)
return true;
return false;
}
vector<STORE> dijkstra(MGraph *G,int from){
STORE TMP;
priority_queue<STORE> Q;
vector<STORE> S;
vector<int> visited(G->n,0);
TMP.node = from;
TMP.parent = from;
TMP.weight = 0;
Q.push(TMP);
S.push_back(TMP);
while(!Q.empty()){
TMP = Q.top();
Q.pop();
for(int i=0;i<G->n;i++)
if(G->edges[TMP.node][i] > 0 && \
visited[TMP.node]==0){
STORE NEWEDGE;
NEWEDGE.node = i;
NEWEDGE.weight = G->edges[TMP.node][i] + TMP.weight;
NEWEDGE.parent = TMP.node;
Q.push(NEWEDGE);
}
visited[TMP.node] = 1;
if(!Q.empty()){
TMP = Q.top();
if(!FIND_STORE(S,TMP))
S.push_back(TMP);
}
for(int i=0;i<S.size();i++)
if(S[i].node == TMP.node){
if(TMP.weight < S[i].weight){
S[i].weight = TMP.weight;
S[i].parent = TMP.parent;
}
}
}
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = dijkstra(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<S[i].node+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}
Bellman-Ford:
#include <iostream>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INFINITE;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int weight;
int parent;
}STORE;
vector<STORE> Bellman_Ford(MGraph *G,int from){
vector<STORE> S(G->n);
for(int i=0;i<G->n;i++){
S[i].weight = INFINITE;
S[i].parent = -1;
}
S[from].weight = 0;
S[from].parent = from;
for(int i=0;i<((G->n)-1);i++)
for(int j=0;j<G->n;j++)
for(int k=0;k<G->n;k++)
if(G->edges[j][k] < INFINITE){
if(S[k].weight > S[j].weight + G->edges[j][k]){
S[k].weight = S[j].weight + G->edges[j][k];
S[k].parent = j;
}
}
for(int i=0;i<G->n;i++)
for(int j=0;j<G->n;j++)
if(S[j].weight > S[i].weight + G->edges[i][j])
goto Negacyclic;
return S;
Negacyclic:
cout<<"There is Negacyclic"<<endl;
S.resize(0);
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = Bellman_Ford(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<i+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}
SPFA:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INFINITE;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int weight;
int parent;
}STORE;
vector<STORE> SPFA(MGraph *G,int from){
queue<int> Q;
vector<int> pushed(G->n,0);
vector<int> count(G->n,0);
vector<STORE> S(G->n);
for(int i=0;i<G->n;i++){
S[i].weight = INFINITE;
S[i].parent = -1;
}
S[from].weight = 0;
S[from].parent = from;
Q.push(from);
pushed[from] = 1;
while(!Q.empty()){
int cur = Q.front();
Q.pop();
count[cur]++;
if(count[cur] >= G->n)
goto Negacyclic;
pushed[cur] = 0;
for(int i=0;i<G->n;i++)
if(S[i].weight > S[cur].weight + G->edges[cur][i] && \
G->edges[cur][i] < INFINITE){
S[i].weight = S[cur].weight + G->edges[cur][i];
S[i].parent = cur;
if(pushed[i] == 0){
Q.push(i);
pushed[i]=1;
}
}
}
return S;
Negacyclic:
cout<<"There is Negacyclic"<<endl;
S.resize(0);
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = SPFA(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<i+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}