connectivity on graph Given a graph, undirected or directed, what is the optimal or just good algorithm for finding the following? 1) Whether two vertices are connected. 2) The shortest path going from one to the other. 3) The longest path going from one to the other with repeating edges or vertices. I can think of a physical algorithm for undirected graph for question 1) and 2). Construct the graph with edges represented by equal length strings. Pick up the given two vertices and pull the construct taut. If the construct does not disintegrate, the answer to 1) is positive, and tracing the straight line between the two vertices is the shortest path. However, how does one translate this physical algorithm to a mathematical one? What about directed graph and question 3)?

[All links below are Wikipedia pages.]

1) Depth-first search or breadth-first search works. For more info, see this.

2) See this. If the edges are unweighted, then breadth-first search works. Otherwise, Dijkstra's algorithm is the natural generalization.

3) According to this, the problem is NP-hard. I don't know much about this, so maybe someone else can comment.