Как описать возможные маршруты между 2 узлами с использованием псевдокода - PullRequest
Новая
       29

Как описать возможные маршруты между 2 узлами с использованием псевдокода

0 голосов
/ 08 мая 2019

Я пытаюсь разработать алгоритм, использующий псевдокод для отображения всех возможных маршрутов между 2 узлами. Я посмотрел на алгоритм dijkstra, но у меня возникли некоторые трудности при попытке создать алгоритм с использованием только псевдокода.

Возможные маршруты между узлами 7 и 5

Я определил все возможные маршруты (без прохождения одного и того же узла дважды)

7 -> 4 -> 5

7 -> 6 -> 2 -> 1 -> 8 -> 5

7-> 6 -> 4 -> 5

7 -> 6 -> 2 -> 1 -> 3 -> 5

Набор узлов: 1,2,3,4,5,6,7,8

Связь между узлами 1 + 2, 1 + 3, 1 + 8, 2 + 6, 3 + 5, 4 + 5, 4 + 6, 4 + 7, 5 + 8, 6 + 7.

1 Ответ

0 голосов
/ 19 июня 2019

Использование DFS: Идея состоит в том, чтобы сделать первый проход глубины заданного направления граф. Начните обход от источника. Продолжайте хранить посещенные вершины в массиве говорят «путь []». Если мы достигнем вершины назначения, напечатать содержимое пути []. Важно отметить текущее вершины в пути [] также посещены, так что обход не идет в цикле. 

Java Implementation:

// Prints all paths from
    // 's' to 'd'
    public void printAllPaths(int s, int d) 
    {
        boolean[] isVisited = new boolean[v];
        ArrayList pathList = new ArrayList<>();

        //add source to path[]
        pathList.add(s);

        //Call recursive utility
        printAllPathsUtil(s, d, isVisited, pathList);
    }

    // A recursive function to print
    // all paths from 'u' to 'd'.
    // isVisited[] keeps track of
    // vertices in current path.
    // localPathList<> stores actual
    // vertices in the current path
    private void printAllPathsUtil(Integer u, Integer d,
                                    boolean[] isVisited,
                            List localPathList) {

        // Mark the current node
        isVisited[u] = true;

        if (u.equals(d)) 
        {
            System.out.println(localPathList);
        }

        // Recur for all the vertices
        // adjacent to current vertex
        for (Integer i : adjList[u]) 
        {
            if (!isVisited[i])
            {
                // store current node 
                // in path[]
                localPathList.add(i);
                printAllPathsUtil(i, d, isVisited, localPathList);

                // remove current node
                // in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited[u] = false;
    }

Вы можете проверить другие способы здесь https://efficientcodeblog.wordpress.com/2018/02/15/finding-all-paths-between-two-nodes-in-a-graph/

...