Skip to content

Commit 32a2581

Browse files
liuyuboboboliuyubobobo
committed
bellman ford algo test codes support starting from various source.
1 parent 45eafa7 commit 32a2581

File tree

6 files changed

+30
-10
lines changed

6 files changed

+30
-10
lines changed

‎09-Shortest-Path/Course Code (C++)/05-Implementation-of-Bellman-Ford/BellmanFord.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ class BellmanFord{
4848

4949
// 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
5050
distTo[s] = Weight();
51-
from[s] = new Edge<Weight>(s, s, 0); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
51+
from[s] = new Edge<Weight>(s, s, Weight()); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
5252

5353
// Bellman-Ford的过程
5454
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离

‎09-Shortest-Path/Course Code (C++)/05-Implementation-of-Bellman-Ford/main.cpp

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,16 @@ int main() {
1717
ReadGraph<SparseGraph<int>, int> readGraph(g, filename);
1818

1919
cout<<"Test Bellman-Ford:"<<endl<<endl;
20-
BellmanFord<SparseGraph<int>, int> bellmanFord(g,0);
20+
21+
int s = 0;
22+
BellmanFord<SparseGraph<int>, int> bellmanFord(g, s);
2123
if( bellmanFord.negativeCycle() )
2224
cout<<"The graph contain negative cycle!"<<endl;
2325
else
24-
for( int i = 1 ; i < V ; i ++ ) {
26+
for( int i = 0 ; i < V ; i ++ ) {
27+
if(i == s)
28+
continue;
29+
2530
if (bellmanFord.hasPathTo(i)) {
2631
cout << "Shortest Path to " << i << " : " << bellmanFord.shortestPathTo(i) << endl;
2732
bellmanFord.showPath(i);

‎09-Shortest-Path/Course Code (C++)/Chapter-09-Completed-Code/BellmanFord.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ class BellmanFord{
4848

4949
// 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
5050
distTo[s] = Weight();
51-
from[s] = new Edge<Weight>(s, s, 0); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
51+
from[s] = new Edge<Weight>(s, s, Weight()); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
5252

5353
// Bellman-Ford的过程
5454
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离

‎09-Shortest-Path/Course Code (C++)/Chapter-09-Completed-Code/main_bellmanford.cpp

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,16 @@ int main() {
1717
ReadGraph<SparseGraph<int>, int> readGraph(g, filename);
1818

1919
cout<<"Test Bellman-Ford:"<<endl<<endl;
20-
BellmanFord<SparseGraph<int>, int> bellmanFord(g,0);
20+
21+
int s = 0;
22+
BellmanFord<SparseGraph<int>, int> bellmanFord(g, s);
2123
if( bellmanFord.negativeCycle() )
2224
cout<<"The graph contain negative cycle!"<<endl;
2325
else
24-
for( int i = 1 ; i < V ; i ++ ) {
26+
for( int i = 0 ; i < V ; i ++ ) {
27+
if(i == s)
28+
continue;
29+
2530
if (bellmanFord.hasPathTo(i)) {
2631
cout << "Shortest Path to " << i << " : " << bellmanFord.shortestPathTo(i) << endl;
2732
bellmanFord.showPath(i);

‎09-Shortest-Path/Course Code (Java)/05-Implementation-of-Bellman-Ford/src/bobo/algo/Main.java

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,11 +13,16 @@ public static void main(String[] args) {
1313
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
1414

1515
System.out.println("Test Bellman-Ford:\n");
16-
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g,0);
16+
17+
int s = 0;
18+
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
1719
if( bellmanFord.negativeCycle() )
1820
System.out.println("The graph contain negative cycle!");
1921
else
20-
for( int i = 1 ; i < V ; i ++ ){
22+
for( int i = 0 ; i < V ; i ++ ){
23+
if(i == s)
24+
continue;
25+
2126
if(bellmanFord.hasPathTo(i)) {
2227
System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
2328
bellmanFord.showPath(i);

‎09-Shortest-Path/Course Code (Java)/Chapter-09-Completed-Code/src/bobo/algo/BellmanFord.java

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -137,11 +137,16 @@ public static void main(String[] args) {
137137
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
138138

139139
System.out.println("Test Bellman-Ford:\n");
140-
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g,0);
140+
141+
int s = 0;
142+
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
141143
if( bellmanFord.negativeCycle() )
142144
System.out.println("The graph contain negative cycle!");
143145
else
144-
for( int i = 1 ; i < V ; i ++ ){
146+
for( int i = 0 ; i < V ; i ++ ){
147+
if(i == s)
148+
continue;
149+
145150
if(bellmanFord.hasPathTo(i)) {
146151
System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
147152
bellmanFord.showPath(i);

0 commit comments

Comments
 (0)