For further info goto : http://securityresearch.in/beta/
1: // Bellman_Ford.cpp
2: //
3: // Copyright 2010 ananya <ananya@ananya-laptop>
4: //
5: // This program is free software; you can redistribute it and/or modify
6: // it under the terms of the GNU General Public License as published by
7: // the Free Software Foundation; either version 2 of the License, or
8: // (at your option) any later version.
9: //
10: // This program is distributed in the hope that it will be useful,
11: // but WITHOUT ANY WARRANTY; without even the implied warranty of
12: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13: // GNU General Public License for more details.
14: //
15: // You should have received a copy of the GNU General Public License
16: // along with this program; if not, write to the Free Software
17: // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
18: // MA 02110-1301, USA.
19: #include <iostream>
20: #include <stdio.h>
21: #include <limits.h>
22: #include <map>
23: #include <vector>
24: #include <string>
25: #include <list>
26: #include <functional>
27: using namespace std;
28: struct Vertex;
29: struct Edge
30: {
31: Vertex *dest;
32: double cost;
33: Edge(Vertex *d=0,double c=0.0)
34: : dest(d),cost(c){}
35: };
36: struct Vertex
37: {
38: string name;
39: vector<Edge> adj;
40: double dist;
41: Vertex *prev;
42: unsigned int scratch;
43: Vertex(const string &nam):name(nam)
44: {reset();}
45: void reset()
46: {
47: dist=3000000;
48: prev=0;
49: scratch=0;
50: }
51: };
52: class Graph
53: {
54: public:
55: Graph(){};
56: ~Graph();
57: void addEdge(const string & sourceName,const string & destName,double cost);
58: void printPath(const string & destName) const;
59: bool bellmanFord(const string & startName);
60: void printbellmanFord();
61: private:
62: Vertex * getVertex(const string & vertexName);
63: void printPath(const Vertex & dest) const;
64: void clearAll();
65: typedef map<string,Vertex *,less<string> > vmap;
66: vmap vertexMap;
67: };
68: Graph::~Graph()
69: {
70: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
71: delete (*itr).second;
72: }
73: Vertex * Graph::getVertex(const string & vertexName)
74: {
75: vmap::iterator itr=vertexMap.find(vertexName);
76: if(itr==vertexMap.end())
77: {
78: Vertex *newv=new Vertex(vertexName);
79: vertexMap[vertexName]=newv;
80: return newv;
81: }
82: return (*itr).second;
83: }
84: void Graph::addEdge(const string & sourceName,
85: const string & destName,double cost)
86: {
87: Vertex *v=getVertex(sourceName);
88: Vertex *w=getVertex(destName);
89: v->adj.push_back(Edge(w,cost));
90: }
91: void Graph::clearAll()
92: {
93: for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)
94: (*itr).second->reset();
95: }
96: void Graph::printPath(const Vertex & dest) const
97: {
98: if(dest.prev!=0)
99: {
100: printPath(*dest.prev);
101: cout<<" -->";
102: }
103: cout<<dest.name;
104: }
105: void Graph::printPath(const string &destName) const
106: {
107: vmap::const_iterator itr=vertexMap.find(destName);
108: if(itr==vertexMap.end())
109: {
110: cout<<destName<<" not Found in Graph"<<endl;
111: return;
112: }
113: Vertex & w =*(*itr).second;
114: if(w.dist==3000000)
115: cout<<destName<<" is not rechable"<<endl;
116: else
117: {
118: cout<<"(Cost is: "<<w.dist<< ")";
119: printPath(w);
120: }
121: cout<<endl;
122: }
123: void Graph::printbellmanFord()
124: {
125: for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)
126: {
127: cout<<(*itr).first;
128: printPath((*itr).first);
129: }
130: }
131: bool Graph::bellmanFord(const string & startName)
132: {
133: vmap::iterator itr=vertexMap.find(startName);
134: if(itr==vertexMap.end())
135: {
136: cout<<"Specified node not found in graph"<<endl;
137: return 0;
138: }
139: clearAll();
140: Vertex *start=(*itr).second;
141: list<Vertex *> q;
142: q.push_back(start);
143: start->dist=0;
144: start->scratch++;
145: while(!q.empty())
146: {
147: Vertex *v=q.front();
148: q.pop_front();
149: if(v->scratch++>2*vertexMap.size())
150: {
151: cout<<"Negative Cycle detected"<<endl;
152: return false ;
153: }
154: for(unsigned int i=0;i<v->adj.size();i++)
155: {
156: Edge e=v->adj[i];
157: Vertex *w=e.dest;
158: double cvw=e.cost;
159: if(w->dist>v->dist+cvw)
160: {
161: w->dist=v->dist+cvw;
162: w->prev=v;
163: if(w->scratch++ % 2==0)
164: q.push_back(w);
165: else
166: w->scratch++;
167: }
168: }
169: }
170: return true ;
171: }
172: int main(int argc, char** argv)
173: {
174: Graph g;
175: cout<<"Enter the Graph description in following format:->"<<endl;
176: cout<<"Edge_sourceName Edge_destName cost_of_Edge"<<endl;
177: cout<<"Enter the detail:-"<<endl;
178: int a,cost;
179: a=1;
180: string sName,dName;
181: while(a==1)
182: {
183: cin>>sName>>dName>>cost;
184: g.addEdge(sName,dName,cost);
185: cout<<"Wanna Continue(press 1/0):";
186: cin>>a;
187: }
188: cout<<"Enter the source node:";
189: cin>>sName;
190: if(g.bellmanFord(sName)==true)
191: {
192: cout<<"Shortest path to Distinct nodes are :-->"<<endl;
193: g.printbellmanFord();
194: }
195: else
196: {
197: }
198: return 0;
199: }
