For any graph , with a source vertex and non-negative edge lengths, shortest paths from s to all other vertices can be captured via a rooted spanning out-tree (branching).

Any prefix of a shortest path is a shortest path.

We can find shortest path in un-weighted graphs using DFS.

Multiplying every edge weight by a positive constant, does not change the solution to the single-source shortest-paths problem. (i.e., we pick a constant and for every edge ,  weight() changes to weight()).

Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. (i.e., we pick a constant and for every edge ,  weight() changes to weight() + ).

We need at least memory to store all pairs shortest path.

We can use Dijkstra's algorithm to find the shortest path in edge-weighted graph, even if we have negative weights as long as there is no negative cycle.

The table entry in the Floyd-Warshall algorithm stores the distance of the shortest path from vertex to vertex that goes through the vertex .

We can detect existence of a negative cycle in the graph using Floyd-Warshall algorithm.

After creating a DFS Tree for a graph G, every edge of G is either also an edge in DFS tree or it is a back edge.

The running time of BFS on a graph with vertices and edges represented by an adjacency-matrix is .

In unweighted graph, for any vertex v reachable from s, BFS(s) computes a shortest path from s to v (no path from s to v has fewer edges).

Given an adjacency-matrix representation of the graph, we can compute the degree of a vertex v in O(deg(v)) time, where deg(v) is degree of the vertex v.

In unweighted graph, for any vertex v reachable from s, DFS(s) computes a shortest path from s to v (no path from s to v has fewer edges).