Dijkstra的算法找到所有可能的最短路径 [英] Dijkstra's algorithm to find all the shortest paths possible

问题描述

我正在研究Dijkstra的算法，我真的需要找到所有可能的最短路径，而不仅仅是一条。我使用的是邻接矩阵，我应用了Dijkstra的算法，我可以找到最短路径。但我需要以最低的成本找到所有的路径，我的意思是所有可能的解决方案，如果它们存在的话。

这就是我的算法的工作方式，对于单个解决方案：

  public void dijkstra（int graph [] []）
 {
 int d [] = new int [graph.length]; 
 int dC [] = new int [graph.length]; 
 int p [] = new int [graph.length]; 
 
 for（int i = 0; i  d [i] = 100; dC [i] = 100; p [i] = -1; 
} 
 d [0] = 0; dC [0] = 0; 
 
 int i = 0，min = 200，po​​s = 0; //你可以将min改为1000，使其成为最大数
，同时（i  //提取最小
（int j = 0; j< ; dC.length; j ++）{
 if（min> d [j]& dC [j]！= -1）{
 min = d [j] pos = j; 
} 
} 
 dC [pos] = -1; 
 
 //放宽
（int j = 0; j  if（d [j]> graph [pos] [j ] + d [pos]）{
d [j] = graph [pos] [j] + d [pos]; 
 p [j] = pos; 
} 
} 
 i ++; min = 200; 
} 
 
 for（int j = 0; j  System.out.print（p [j] +）; 
} 
 System.out.print（\\\
）; 
 for（int j = 0; j  System.out.print（d [j] +）; 
} 
 System.out.print（\\\
）; 
 
  

解决方案

如果你看看Dijkstra算法在这里伪代码形式：
维基百科Dijkstra的算法伪代码

您会注意到这条线被称为放松。现在它只包含一个案例，用于找到的路径小于当前最短路径，但如果它们 ，则不会执行任何操作。您应该保留列表中所有同样短的路径。

I'm working on Dijkstra's algorithm, and I really need to find all the possible shortest paths, not just one. I'm using an adjacency matrix and I applied Dijkstra's algorithm, and I can find the shortest path. But I need to find all the paths with that minimum cost, I mean all the possible solutions, if they exist.

This is how my algorithm works, for a single solution:

public void dijkstra( int graph[][] )
{
    int d[] = new int[ graph.length ];
    int dC[] = new int[ graph.length ];
    int p[] = new int[ graph.length ];

    for( int i = 0; i < graph.length; i++ ){
        d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
    }
    d[ 0 ] = 0; dC[ 0 ] = 0;

    int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
    while( i < graph.length ){
        //extract minimum
        for( int j = 0; j < dC.length; j++ ){
            if( min > d[ j ] && dC[ j ] != -1 ){
                min = d[ j ]; pos = j;
            }
        }
        dC[ pos ] = -1;

        //relax
        for( int j = 0; j < graph.length; j++ ){
            if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                d[ j ] = graph[ pos ][ j ] + d[ pos ];
                p[ j ] = pos;
            }
        }
        i++; min = 200;
    }

    for( int j = 0; j < p.length; j++ ){
        System.out.print( p[ j ] + " " );
    }
    System.out.print( "\n" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "\n" );
}

解决方案

If you look at Dijkstra's algorithm in pseudocode form here: Wikipedia Dijkstra's Algorithm Pseudocode

You will notice the line referred to as a Relax. Right now it only contains a case for if the path found is less than the current shortest path, but there isn't anything done if they are equal. You should probably keep all the equally short paths in a List.

这篇关于Dijkstra的算法找到所有可能的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！