Кратчайший путь Флойда для ненаправленного графа - PullRequest
Новая
       68

Кратчайший путь Флойда для ненаправленного графа

0 голосов
/ 14 января 2019

Я реализовал программу, которая может вычислять кратчайшие пути для любого графа либо с помощью алгоритма Флойда / Дейкстры, основанного на пользовательском вводе.

Оба алгоритма отлично работают для ориентированного графа. Выход должен отображать 1) фактический путь, который нужно взять из начальной вершины 2) Кратчайшее расстояние, которое нужно преодолеть

Но когда дело доходит до неориентированного графа, у меня возникают проблемы.

Мой график представлен не матрицей смежности, а классами Graph и Edge, как показано ниже 

class Graph
{
    private final int noOfVertices;
    private final ArrayList<Edge> edges = new ArrayList<Edge>();
    private boolean undirected = false;

    Graph(int vertexCount)
    {
        noOfVertices = vertexCount;
        edges.ensureCapacity(2 * (vertexCount - 1));
    }

    public int getWeight(int src,int dst)
    {
     int weight=90000;

     for(Edge edge:edges)
     {
      if(edge.src==src && edge.dst==dst)
      {
       weight=edge.weight;
       break;
      }
     }

     return weight;
    }

    public int getEdgeCount(){return edges.size();}
    public int getVertexCount(){return noOfVertices;}

    public static class Edge
    {
        public int src;
        public int dst;
        public int weight;

        Edge(int v1, int v2, int w)
        {
            src = v1;
            dst = v2;
            weight = w;
        }
    }
}

Для реализации неориентированного графа этот код используется ниже 

void newEdge(int src,int dst,int weight)
{
    edges.add(new Edge(src,dst,weight));
    if(undirected){ edges.add(new Edge(dst,src,weight));}
}

Теперь алгоритм Дейкстры отлично работает на этой установке, но когда я использую алгоритм Флойда, я начинаю получать неверный путь, но правильное расстояние

Это алгоритм моего Флойда 

public static Integer[] Floyd(Graph graph, int startVertex, int endVertex)
{
    ArrayList<Integer> pathInfo = new ArrayList<Integer>();
    int dist[][] = new int[graph.getVertexCount()][graph.getVertexCount()];
    int path[][] = new int[graph.getVertexCount()][graph.getVertexCount()];

    int V = graph.getVertexCount();
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (i == j)
            {
                dist[i][j] = 0;
            }
            else
            {
                dist[i][j] = graph.getWeight(i, j);
            }/*Initialize with edge weight's between vertices i,j.If edge does not exist graph.getWeight() return's 90000 i.e simply an value somewhat close to infinite because when I use Integer.MAX_VALUE I get negative distance's when doing dist[i][k]+dist[k][j] so i avoid it*/
            path[i][j] = j;
        }
    }

    /*actual Floyd's algorithm*/
    for (int k = 0; k < V; k++)
    {
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k; /*if path exist's record the intermediate vertex*/
                }
            }
        }
    }

    int currentVertex=endVertex;  /*Start from last vertex*/
    int nextVertex=path[startVertex][endVertex];/*Find path*/

    pathInfo.add(currentVertex);/*Add Current Vertex*/
    while(currentVertex!=nextVertex)/*Backtrack until the vertex we are currently at and the next vertex we need to go to from there are the same which mean's we have reached our target*/
    {
      currentVertex=nextVertex;
      pathInfo.add(0,currentVertex);
      nextVertex=path[startVertex][nextVertex];
    }
    pathInfo.add(0,startVertex);/*Finally add the vertex we ended at*/

    pathInfo.add(dist[startVertex][endVertex]);/*Come's out correct in both cases*/

    return pathInfo.toArray(new Integer[]{});/*Convert info to array*/
}

Итак, вот мой неориентированный граф, приведенный ниже. Пунктирные линии представляют собой ребро, которое идет в обоих направлениях. 

0--1--2--3

Каждый край имеет вес 2

Теперь, когда я вызываю алгоритм Флойда с начальной вершиной = 0 и конечной вершиной = 3 Я получаю правильный выходной путь. 

0,1,2,3

Но когда я снова вызываю алгоритм Флойда с началом Vertex = 3 и концом Vertex = 0 Выходной путь 

3,2,0

Вершина 1 отсутствует.

Но с помощью алгоритма Дейкстры я получаю правильный результат в обоих случаях

Вот матрица пути, рассчитанная выше. 

 0   1   1   2   
 0   1   2   2   
 1   1   2   3   
 2   2   2   3

Расстояние получается правильным, равным 6 в обоих случаях, но путь неверен, когда я меняю порядок вершин только для алгоритма Флойда.

Большинство видео идей были включены по этой ссылке https://www.bing.com/videos/search?q=floyd%27s+algorithm&&view=detail&mid=E17F409B3AB0B2307233E17F409B3AB0B2307233&&FORM=VRDGAR

Есть идеи, где я ошибся?

...