Перед тем, как откликнется Флойд-Варшалл / Дейкстра, ответьте, пожалуйста, позвольте мне объяснить ситуацию, так как я уверен, что любой алгоритм может быть настроен для этого случая, и это должно быть, так как это не пример программы для игрушек (учтите, что , в Java, так что держать его управляемым памяти)
То, что у меня есть, это веб-граф, сгенерированный из узла 0 в узел n, узел 3 не может связываться с узлом 5, потому что узел 5 не существовал, когда узел 3 выбирал свои ссылки . Каждый «узел» представлен в виде in_neighbours [nodeID] и out_neighbours [nodeID], скажем, nodeId = 3, поэтому мы говорим об узле 3. Обратите внимание также, что in_ / out_ оба отсортированы, (in_ естественно сортируется, поскольку 5 выберет все его ссылки сразу, только тогда 6 выберет out_links, поэтому 3 in_'s никогда не могут содержать {6, 5, 7}), а ofc оба могут содержать дубликаты. (in / out - массивы ArrayList размера n, где out_ всегда имеет размер d или m, который вместе с n указывается при запуске пользователем)
Нет весов. Что я должен сделать, это найти среднее расстояние ()
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 & i, а не все расстояния одновременно (недостаточно памяти, оно будет проверено при 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;
}
Так что я спрашиваю, связывает ли «более свежий» (ofc на этом этапе график) узел i с любым из его более ранних друзей напрямую, если да, расстояние равно 1 прыжку.
Это только я, или «кратчайший» путь всегда будет первым найденным путем, если узлы пройдены назад?
Как мне проверить, не его ли 1, "else" после базового случая? Моя математика довольно слабая, пожалуйста, будьте нежны :)
Любые советы, как использовать тот факт, что ссылки отсортированы?
Это не домашняя работа или что-то, от чего я пытаюсь обмануть, речь идет не о самом коде, это должен быть полезный инструмент , «обучение» приходит само по себе.
вот как граф выглядит в виде идентификатора узла, идентификаторов ссылок в ссылках для 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;
}