Я написал некоторый Java-код для проверки подхода DFS, который я предложил: код не проверяет пути в диапазоне, а печатает все пути.Это должно быть просто изменить код, чтобы сохранить только те, которые находятся в диапазоне.Я также провел несколько простых тестов.Кажется, он дает правильные результаты с 10 вершинами и 50 ребрами или около того, хотя я не нашел времени для тщательного тестирования.Я также запустил его для 100 вершин и 1000 ребер.Он не исчерпывает память и продолжает печатать новые пути, пока я не убью его, а таких много.Это неудивительно для случайно сгенерированных плотных графов, но может не иметь место для графов реального мира, например, когда степени вершин следуют степенному закону (особенно с узкими диапазонами весов. Кроме того, если вам просто интересно, как распределяются длины путив диапазоне вы можете остановиться после того, как вы сгенерировали определенное число.
Программа выводит следующее: a) список смежности случайно сгенерированного графа.б) Набор всех путей, которые он нашел до сих пор.
public class AllPaths {
int numOfVertices;
int[] status;
AllPaths(int numOfVertices){
this.numOfVertices = numOfVertices;
status = new int[numOfVertices+1];
}
HashMap<Integer,ArrayList<Integer>>adjList = new HashMap<Integer,ArrayList<Integer>>();
class FoundSubpath{
int pathWeight=0;
int[] vertices;
}
// For each vertex, a a list of all subpaths of length less than UB found.
HashMap<Integer,ArrayList<FoundSubpath>>allSubpathsFromGivenVertex = new HashMap<Integer,ArrayList<FoundSubpath>>();
public void printInputGraph(){
System.out.println("Random Graph Adjacency List:");
for(int i=1;i<=numOfVertices;i++){
ArrayList<Integer>toVtcs = adjList.get(new Integer(i));
System.out.print(i+ " ");
if(toVtcs==null){
continue;
}
for(int j=0;j<toVtcs.size();j++){
System.out.print(toVtcs.get(j)+ " ");
}
System.out.println(" ");
}
}
public void randomlyGenerateGraph(int numOfTrials){
Random rnd = new Random();
for(int i=1;i < numOfTrials;i++){
Integer fromVtx = new Integer(rnd.nextInt(numOfVertices)+1);
Integer toVtx = new Integer(rnd.nextInt(numOfVertices)+1);
if(fromVtx.equals(toVtx)){
continue;
}
ArrayList<Integer>toVtcs = adjList.get(fromVtx);
boolean alreadyAdded = false;
if(toVtcs==null){
toVtcs = new ArrayList<Integer>();
}else{
for(int j=0;j<toVtcs.size();j++){
if(toVtcs.get(j).equals(toVtx)){
alreadyAdded = true;
break;
}
}
}
if(!alreadyAdded){
toVtcs.add(toVtx);
adjList.put(fromVtx, toVtcs);
}
}
}
public void addAllViableSubpathsToMap(ArrayList<Integer>VerticesTillNowInPath){
FoundSubpath foundSpObj;
ArrayList<FoundSubpath>foundPathsList;
for(int i=0;i<VerticesTillNowInPath.size()-1;i++){
Integer startVtx = VerticesTillNowInPath.get(i);
if(allSubpathsFromGivenVertex.containsKey(startVtx)){
foundPathsList = allSubpathsFromGivenVertex.get(startVtx);
}else{
foundPathsList = new ArrayList<FoundSubpath>();
}
foundSpObj = new FoundSubpath();
foundSpObj.vertices = new int[VerticesTillNowInPath.size()-i-1];
int cntr = 0;
for(int j=i+1;j<VerticesTillNowInPath.size();j++){
foundSpObj.vertices[cntr++] = VerticesTillNowInPath.get(j);
}
foundPathsList.add(foundSpObj);
allSubpathsFromGivenVertex.put(startVtx,foundPathsList);
}
}
public void printViablePaths(Integer v,ArrayList<Integer>VerticesTillNowInPath){
ArrayList<FoundSubpath>foundPathsList;
foundPathsList = allSubpathsFromGivenVertex.get(v);
if(foundPathsList==null){
return;
}
for(int j=0;j<foundPathsList.size();j++){
for(int i=0;i<VerticesTillNowInPath.size();i++){
System.out.print(VerticesTillNowInPath.get(i)+ " ");
}
FoundSubpath fpObj = foundPathsList.get(j) ;
for(int k=0;k<fpObj.vertices.length;k++){
System.out.print(fpObj.vertices[k]+" ");
}
System.out.println("");
}
}
boolean DfsModified(Integer v,ArrayList<Integer>VerticesTillNowInPath,Integer source,Integer dest){
if(v.equals(dest)){
addAllViableSubpathsToMap(VerticesTillNowInPath);
status[v] = 2;
return true;
}
// If vertex v is already explored till destination, just print all subpaths that meet criteria, using hashmap.
if(status[v] == 1 || status[v] == 2){
printViablePaths(v,VerticesTillNowInPath);
}
// Vertex in current path. Return to avoid cycle.
if(status[v]==1){
return false;
}
if(status[v]==2){
return true;
}
status[v] = 1;
boolean completed = true;
ArrayList<Integer>toVtcs = adjList.get(v);
if(toVtcs==null){
status[v] = 2;
return true;
}
for(int i=0;i<toVtcs.size();i++){
Integer vDest = toVtcs.get(i);
VerticesTillNowInPath.add(vDest);
boolean explorationComplete = DfsModified(vDest,VerticesTillNowInPath,source,dest);
if(explorationComplete==false){
completed = false;
}
VerticesTillNowInPath.remove(VerticesTillNowInPath.size()-1);
}
if(completed){
status[v] = 2;
}else{
status[v] = 0;
}
return completed;
}
}
public class AllPathsCaller {
public static void main(String[] args){
int numOfVertices = 20;
/* This is the number of attempts made to create an edge. The edge is usually created but may not be ( eg, if an edge already exists between randomly attempted source and destination.*/
int numOfEdges = 200;
int src = 1;
int dest = 10;
AllPaths allPaths = new AllPaths(numOfVertices);
allPaths.randomlyGenerateGraph(numOfEdges);
allPaths.printInputGraph();
ArrayList<Integer>VerticesTillNowInPath = new ArrayList<Integer>();
VerticesTillNowInPath.add(new Integer(src));
System.out.println("List of Paths");
allPaths.DfsModified(new Integer(src),VerticesTillNowInPath,new Integer(src),new Integer(dest));
System.out.println("done");
}
}
Я думаю, что вы на правильном пути с BFS.Я придумал какой-то грубый, смутно похожий на Java псевдокод для предложенного решения с использованием BFS.Идея состоит в том, чтобы сохранить подпути, найденные во время предыдущих обходов, и их длины для повторного использования.Сегодня я попытаюсь улучшить код, когда найду время, но, надеюсь, это даст ключ к пониманию того, куда я иду с этим.Я предполагаю, что сложность должна быть порядка O (E).
,
Дополнительные комментарии:
Это кажется разумным подходом, хотя я не уверен, что полностью понимаю.Я построил простой пример, чтобы убедиться, что я делаю.Рассмотрим простой граф со всеми ребрами, взвешенными по 1, и представление списка смежности следующим образом:
A-> B, C
B-> C
C-> D, F
F-> D
Допустим, мы хотели найти все пути от A до F, а не только те, которые находятся в диапазоне, и вершины назначения из исходной вершины исследуются в алфавитном порядке.Тогда алгоритм будет работать следующим образом:
Сначала начинается с B: ABCDF ABCF
Затем начинается с C: ACDF ACF
Это правильно?
В этом случае простым улучшением будет сохранение для каждой посещенной вершины путей, найденных после первого посещения этого узла.Например, в этом примере, когда вы посещаете C из B, вы обнаружите, что есть два пути к F из C: CF и CDF.Вы можете сохранить эту информацию, и в следующей итерации, как только вы достигнете C, вы можете просто добавить CF и CDF к найденному пути, и вам не нужно будет исследовать его дальше.
Чтобы найти ребра в диапазонеВы можете использовать условия, которые вы уже описали, для путей, сгенерированных как указано выше.
Еще одна мысль: может быть, вам не нужно запускать Dijkstra's, чтобы вообще найти кратчайшие пути.Длина подпути будет найдена при первом прохождении подпути.Таким образом, в этом примере длина CDF и CF при первом посещении C через B. Эта информация может быть использована для обрезки при следующем посещении C непосредственно через A. Эта длина будет более точной, чем найденная Дейкстрой,поскольку это будет точное значение, а не нижняя граница.
Дополнительные комментарии: Алгоритм может быть улучшен с некоторой продуманностью.Например, каждый раз, когда шаг релаксации выполняется в алгоритме Дейкстры (шаги 16-19 в описании википедии ), отклоненный старый / более новый подпуть может быть запомнен с использованием некоторой структуры данных, если более старый путь являетсявероятный кандидат (меньше верхней границы).В конце концов, должна быть возможность восстановить все отклоненные пути и сохранить их в пределах досягаемости.
Этот алгоритм должен быть O (V ^ 2).
Я думаю, что посещение каждой вершины только один раз может быть слишком оптимистичным: алгоритмы, такие как кратчайший путь Джикстры, имеют сложность v ^ 2 длянайти единственный путь, кратчайший путь.Поиск всех путей (включая кратчайший путь) является более сложной задачей, поэтому должен иметь сложность не менее V ^ 2.
Моя первая мысль о подходе к проблеме - это вариация алгоритма кратчайшего пути Джикстры. Применение этого алгоритма один раз даст вам длину кратчайшего пути. Это дает вам нижнюю границу длины пути между двумя вершинами. Одновременное удаление ребра из этого кратчайшего пути и пересчет кратчайшего пути должны дать вам несколько более длинные пути.
В свою очередь, края могут быть удалены из этих немного более длинных путей, чтобы генерировать больше путей и так далее. Вы можете остановиться, если у вас есть достаточное количество путей, или если пути, которые вы генерируете, находятся за вашей верхней границей.
Это мое первое предположение. Я новичок в stackoverflow: любые отзывы приветствуются.