algorithm for finding all paths between two vertices without repetitions in the digraph
Please help me make an algorithm for finding all paths between two vertices (vertices should not be repeated in paths), preferably in c#. Example of a graph in the picture, each edge has a weight (w1-w4). You need, for example, to find the paths from the 0th(leftmost) to the 2nd (rightmost). For a given graph, the result should be two rows w1w2 and w3w2 (edge weights).
In the program, I represent the graph as a list of adjacencies.
Made a class that stores the final vertex and the length of the path to it.
This graph in my program is described as follows:
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 });
I tried to make such a function for finding paths, it works for this graph, but if you add vertices, then no, I didn't have enough sense for more.
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;
}
1 answers
The easiest way to solve such problems (if there are really not many vertices) is recursively. Moreover, if there are not many edges, then make a simple "fake" list of adjacency. For example, select the matrix А[n+1][m+1], where n is the number of vertices and m is the number of edges. In this list, the ENDS of the edges are listed as follows: the array A[i] contains the ends of the edges that exit from the vertex i, and the number 0 in the list will indicate the end of the list (we count the vertices from 1). In your case, the matrix it will be like this (I will number the vertices from left to right of 1):
A[1]={2, 2, 0};
A[2]={3, 0};
A[3]={1, 0};
Similarly, we start the matrix W, where the weights of the edges will be in the corresponding places, but only zeros at the end are no longer needed:
W[1]={w1, w3};
W[2]={w2};
W[3]={w4};
Next, we will organize a complete search of all the possibilities using recursion. To do this, you will need an auxiliary stack, which stores the vertices that have already been traversed in the recursion. I'm writing a schematic code for such a function. I write as if I need to output the vertex numbers, but you can do it yourself think about how to output the weights of the edges (that is, I do not use the W array now). (it is also assumed that there are no cycles in the graph)
function GO (int i) {
Положить i в стэк S.
if (i == конечная вершина) {
вывести содержание стека S как вам нужно // Вывели очередной путь до конечной вершины.
вытолкнуть из S верхнюю вершину
return;
}
for (int k=0; A[i][k] != 0; ++k) {
int j = A[i][k]; // Это вершина j, в которую мы можем перейти из i
GO (j);
}
вытолкнуть из S верхнюю вершину
return;
}
Using this feature is very simple. In the main function code, we write something like this:
Сделать стэк S пустым;
int i = начальная вершина, с которой хотим вести обход;
GO(i);
This is a classic idea of traversing the graph in all possible ways, it can be easily modified for any of your requests. But I suggest that you do this yourself. I'll just tell you what you need. In the for loop, BETWEEN the lines int ... and GO ..., you need to insert another row that adds weight W[i][k] to some other stack T, and after calling GO(j) add a row that pushes out the top element from T.