Skip to content

Instantly share code, notes, and snippets.

@rain1024
Last active October 4, 2015 00:25
Show Gist options
  • Save rain1024/b810bef150606c780a37 to your computer and use it in GitHub Desktop.
Save rain1024/b810bef150606c780a37 to your computer and use it in GitHub Desktop.
algorithm

Graph Search Algorithm

Shortest Path Problem [1]

image

Algorithms

  • Dijkstra's algorithm solves the single-source shortest path problem.
  • Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
  • A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
  • Floyd–Warshall algorithm solves all pairs shortest paths.
  • Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
  • Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.

References

  1. http://en.wikipedia.org/wiki/Shortest_path_problem

K-ary tree

In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.

image

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.[1] Some authors allow the binary tree to be the empty set as well.

image

Challenge

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment