2
$\begingroup$

Suppose we have a connected undirected graph with a positive integer cost assigned to each edge.

Given two verticies, how do we find the set of minimal cost paths between those two nodes? Does this problem have a name? What algorithm should we use?

  • 3
    this is shortest path problem, here you can find answers [Shortest Path Problem](http://en.wikipedia.org/wiki/Shortest_path_problem)2012-04-06

1 Answers 1

1

If you looking for algorithm for all possible shortest paths between two vertices, I'd say that unfortunately this problem has exponential output size, assume graph with $n$ distinct cycles: $C_1,C_2,...C_n$, such that each cycle has $4$ vertices, $\forall i\in [1,n-1]$ $C_i$ is connected to $C_{i+1}$ by one edge $e_i$. internal edges in each cycles are:$v_{i_1}v_{i_2},v_{i_2}v_{i_3},v_{i_3}v_{i_4},v_{i_4}v_{i_1}$ and $e_i = v_{i_3}v_{i+1_1}$. number of shortest path between $v_{1_1}$ and $v_{n_3}$ is $O(2^{n \over 2})$. and because size of graph is $4n$, this causes to exponential number of paths.