Прежде чем Floyd–Warshall/Dijkstra отвечает, что лавинная рассылка входит, позвольте мне объяснить ситуацию, поскольку я уверен, что любой алгоритм может быть настроен для этого случая, и это должно быть, поскольку это не игрушечный пример программы (обратите внимание, в Java, так должны сохранить это управляемым мудрый памятью),
То, что я имею, является веб-графиком, сгенерированным от узла 0 к узлу n, узел 3 не может связаться с узлом 5, потому что узел 5 не существовал, когда узел 3 выбирал, он отсутствует ссылки. Каждый "узел" представлен как in_neighbours [идентификатор узла], и out_neighbours [идентификатор узла] говорят, что nodeId=3, таким образом, мы говорим об узле 3. Обратите внимание также, что in_/out_ оба отсортированы, (in_ естественно отсортирован, поскольку 5 выберет, ссылки внезапно, только затем 6 выберут out_links, таким образом, 3's в _ никогда не сможет содержать {6, 5, 7}), и отдел, оба могут содержать дубликаты. (в / массивы ArrayList размера n, где out_ всегда имеет размер d или m, который наряду с n указан при запуске пользователем),
Никакие веса. То, что я должен сделать, является находкой averageDistance ()
public double getAvgDistance() {
int sum = 0;
for (int i=1; i<n; i++) {
for (int j=0; j < i; j++) {
sum += dist(i, j); // there are duplicates, make sure i skip
}
}
return (double)sum / (double)( ((n*(n-1)) / 2) );
}
Что я имею, до сих пор лучший случай. Обратите внимание, что я хочу только найти расстояние между j и мной, не все расстояния одновременно (недостаточно памяти, это будет протестировано в m=20 d=1 000 000),
private int dist(int i, int j) {
int dist = 0;
for (int link : in_neighbours[j]) {
System.out.print("\nIs "+j+" linked to by "+i);
if (out_neighbours[i].contains(link)) {
System.out.print(" - yes!");
dist = 1;
}
}
return dist;
}
Таким образом, я спрашиваю, является ли "более новым" (отдел в этой точке, график завершается) узел, который я связываю с любым из его приятелей старшего возраста непосредственно если так, расстояние, 1 транзитный участок.
Это - просто я, или 'самый короткий' путь всегда будет первым найденным путем, если узлы будут пересечены назад?
Как я "еще" проверяю если не 1, после основного случая? Моя математика довольно слаба быть нежной :) Какие-либо подсказки, как использовать то, что ссылки отсортированы?
Это не домашняя работа или что-то, от чего я пытаюсь обмануть вокруг, это не о самом коде, это должно быть полезным инструментом, "изучение" происходит отдельно по пути.
вот то, как идентификатор узла взглядов графика, ссылки, в ссылках для m=7 n=13, (отметьте эти 0 циклов, состоят в том, как график инициализируется):
0 | 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 3 4 5 6 6 7 8 9
1 | 0 0 0 0 0 0 0 | 2 2 3 4 5 5 8 12
2 | 0 0 0 0 0 1 1 | 3 3 3 3 3 4 4 4 6 7 8 10
3 | 0 1 2 2 2 2 2 | 4 4 5 5 6 6 7 11
4 | 0 1 2 2 2 3 3 | 5 5 6 8 9 10
5 | 0 1 1 3 3 4 4 | 6 7 8 9 9 11 12
6 | 0 0 2 3 3 4 5 | 7 7 7 8 9 9 12
7 | 0 2 3 5 6 6 6 | 8 9 10 11 11 12
8 | 0 1 2 4 5 6 7 | 10 10 10 11 12
9 | 0 4 5 5 6 6 7 | 10 11 11
10 | 2 4 7 8 8 8 9 | 12 12
11 | 3 5 7 7 8 9 9 |
12 | 1 5 6 7 8 10 10 |
Извините за агонию долго чтение.Править: Неверный код в методах, это - то, что я думаю, корректно теперь.
Пересмотр dist nr2, просто попытайтесь найти, существует ли путь вообще:
private int dist(int i, int j) {
int dist = 0, c = 0, count = 0;
boolean linkExists = false;
for (int link : in_neighbours[j]) {
//System.out.print("\nIs "+j+" linked to by "+i);
if (out_neighbours[i].contains(link)) {
//System.out.print(" - yes!");
dist = 1; // there is a direct link
} else {
while ( c < j ) {
// if there's a path from 0 up to j, check if 'i' links to a node which eventually links to 'j'
if (out_neighbours[i].contains(c) &&
(out_neighbours[c].contains(link) || in_neighbours[c].contains(link) )) {
count++; // yes. and this is one node we had to step through to get closer
linkExists = true;
} else {
linkExists = false; // unreachable, the path was interrupted somewhere on the way
break;
}
c++;
}
if (linkExists) {
dist = count-1; // as 2 nodes are linked with 1 edge
} else {
dist = 0; // no path was found
}
}
}
return dist;
}
Поскольку все ребра имеют одинаковый вес в вашей модели, вы можете использовать поиск BFS , чтобы найти кратчайший путь от S до T.
Это итерационный процесс, начиная с набора # 0, содержащего только исходный узел ({S}). На каждом шаге i вы создаете набор #i, находя все узлы, достижимые из набора (i-1) за один шаг.
Итерация завершается в двух случаях:
1) Когда вы обнаруживаете, что набор #k содержит T. В этом случае вы возвращаете k-1.
2) Когда набор пуст, это означает, что два узла недоступны.
Потребление памяти примерно вдвое превышает количество узлов, поскольку на каждом шаге i вы работаете с двумя наборами (i-1 и i), ограниченными общим количеством узлов.
- РЕДАКТИРОВАТЬ -
Вот возможная реализация (я провел несколько тестов):
private Integer getDist(int i, int j) {
Set<Integer> currentSet = new HashSet<Integer>();
currentSet.add(i);
int dist = 0;
while (true) {
Set<Integer> nextSet = new HashSet<Integer>();
for (Integer currNode : currentSet)
nextSet.addAll(out[currNode]);
if (nextSet.isEmpty())
return null; //i.e. infinite
if (nextSet.contains(j))
return dist;
dist++;
currentSet = nextSet;
}
}
Реализация предполагает, что в и вне определены как Список
Дубликаты, которые у вас есть в списках, здесь ничего не ломают, но они не имеют отношения к алгоритму.