0%

`Bellman-Ford Algorithm` is slower than Dijkstra. But it can handle graph contains a negative cycle.

## Time Complexity: E * V

• E is the number of edges
• V is the number of vertexs

# regular graph with negative weight

``````+-+                  +-+
``````

+-2—–>+1| |4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +–3—–>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

# negative cycle

``````+-+                  +-+
``````

+-2—–>+1+<——-(-1)——+4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +-(-1)—>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

```

`Dijkstra Algorithm` is the known fastest algorithm to find the shortest path in a graph with unbounded non-negative weights.

## Time Complexity: `E + V*log(V)`

• E is the number of edges
• V is the number of vertexs

## Implementation

### Python

I wrote post Binary_Tree_Traversal around two years ago to help me remember how to traversal binary tree iteratively.
The solution in that post is quite simply. But I still have trouble to remember it since the code pattern is slight different within `preorder`, `inorder`, `postorder`.

Eventually, I rewrite the code using similar pattern in `python`.

# Bottom Up Parsing

Source Code

## Chapter 7.1

Simple C++ implementation of BFS based bottom up parser

Unger’s Method