Помогите, пожалуйста, сделать алгоритм поиска всех путей между двумя вершинами (вершины не должны повторяться в путях), желательно на языке c#. Пример графа на картинке, каждое ребро имеет вес (w1-w4). Нужно, например, из 0-ой(самая левая) найти пути во 2-ую (самая правая). Для данного графа результатом должны быть две строки w1w2 и w3w2 (весы ребер).
В программе граф представляю в виде списка смежности.
Сделал класс, который хранит конечную вершину и длину пути в нее.
Данный граф у меня в программе описан так:
var graph = new List<List<Edge>>();
var w1 = new Edge( 1, "W1");
var w3 = new Edge( 1, "W3");
var w2 = new Edge( 2, "W2");
var w4 = new Edge( 1, "-W4");
var w5 = new Edge(0, "-1");
//0-ой элемент - нулевая вершина. Имеет путь в 1ую вершину длиной w1 (вершина w1) и в 1-ую вершину длиной w3 - вершина w3 и тд
graph.Add(new List<Edge>() { w1, w3 } );
graph.Add(new List<Edge>() { w2 });
graph.Add(new List<Edge>() { w4, w5 });
Пытался сделать такую функцию для поиска путей, для данного графа работает, но если добавить вершины, то нет, на больше ума не хватило.
static List<string> ways = new List<string>();
static string func = null;
//<summary>
// Ищет прямые пути X -> Y
//</summary>
static string FindDirectWays(List<List<Edge>> graph, int X, int Y)
{
//Х - номер начальной вершины
// У - номер конечной вершины
foreach(var vertex in graph[X])
{
if (vertex.Vertex == Y)
{
func += vertex.Value;
ways.Add(func);
return func;
}
else
{
func = vertex.Value;
func += FindDirectWays(graph, vertex.Vertex, Y);
}
}
return func;
}