Необходимо найти минимальный и максимальный пути от данной вершины (ее указывает пользователь) до всех остальных вершин в графе.
На входе имеется файл с матрицей смежности, например:
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
На выходе необходимо получить приблизительно в таком формате ответ:
The worst case scenario:
1. 1->3 (1 unit of time)
2. 1->2 (1 unit of time)
3. 2->4 (1 unit of time)
The total time required to broadcast the message in the entire network amounts to 3 units of time
The best case scenario:
1. 1->2 (1 unit of time)
2. 1->3 and2->4(1 unit of time)
The total time required to broadcast the message in the entire network amounts to 2 units of time.
Для нахождения минимального пути я нашла метод Дейкстры, но там на входе нужны количество вершин, ребер, точка старта, список ребер смежности и их вес. Например, для этого примера и начальной точки 1 это:
4 3 1
1 2 1
1 3 1
2 4 1
И тогда вывод будет:
0 1 1 2
1: 1
2: 1 2
3: 1 3
4: 1 2 4
Не совсем то, что надо, но хоть что-то...
вот сам код:
Код:
public class Dex {
private static int INF = Integer.MAX_VALUE / 2;
private int n; //количество вершин в орграфе
private int m; //количествое дуг в орграфе
private ArrayList<Integer> adj[]; //список смежности
private ArrayList<Integer> weight[]; //вес ребра в орграфе
private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
private int dist[]; //массив для хранения расстояния от стартовой вершины
private int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
int start; //стартовая вершина, от которой ищется расстояние до всех других
private BufferedReader cin;
private PrintWriter cout;
private StringTokenizer tokenizer;
//процедура запуска алгоритма Дейкстры из стартовой вершины
private void dejkstra(int s)
{
dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0
for (int iter = 0; iter < n; ++iter)
{
int v = -1;
int distV = INF;
//выбираем вершину, кратчайшее расстояние до которого еще не найдено
for (int i = 0; i < n; ++i)
{
if (used[i])
{
continue;
}
if (distV < dist[i])
{
continue;
}
v = i;
distV = dist[i];
}
//рассматриваем все дуги, исходящие из найденной вершины
for (int i = 0; i < adj[v].size(); ++i)
{
int u = adj[v].get(i);
int weightU = weight[v].get(i);
//релаксация вершины
if (dist[v] + weightU < dist[u])
{
dist[u] = dist[v] + weightU;
pred[u] = v;
}
}
//помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние
used[v] = true;
}
}
//процедура считывания входных данных с консоли
private void readData() throws IOException
{
cin = new BufferedReader(new InputStreamReader(System.in));
cout = new PrintWriter(System.out);
tokenizer = new StringTokenizer(cin.readLine());
n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа
m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа
start = Integer.parseInt(tokenizer.nextToken()) - 1;
//инициализируем списка смежности графа размерности n
adj = new ArrayList[n];
for (int i = 0; i < n; ++i)
{
adj[i] = new ArrayList<Integer>();
}
//инициализация списка, в котором хранятся веса ребер
weight = new ArrayList[n];
for (int i = 0; i < n; ++i)
{
weight[i] = new ArrayList<Integer>();
}
//считываем граф, заданный списком ребер
for (int i = 0; i < m; ++i)
{
tokenizer = new StringTokenizer(cin.readLine());
int u = Integer.parseInt(tokenizer.nextToken());
int v = Integer.parseInt(tokenizer.nextToken());
int w = Integer.parseInt(tokenizer.nextToken());
u--;
v--;
adj[u].add(v);
weight[u].add(w);
}
used = new boolean[n];
Arrays.fill(used, false);
pred = new int[n];
Arrays.fill(pred, -1);
dist = new int[n];
Arrays.fill(dist, INF);
}
//процедура восстановления кратчайшего пути по массиву предком
void printWay(int v)
{
if (v == -1)
{
return;
}
printWay(pred[v]);
cout.print((v + 1) + " ");
}
//процедура вывода данных в консоль
private void printData() throws IOException
{
for (int v = 0; v < n; ++v)
{
if (dist[v] != INF)
{
cout.print(dist[v] + " ");
}
else
{
cout.print("-1 ");
}
}
cout.println();
for (int v = 0; v < n; ++v)
{
cout.print((v + 1) + ": ");
if (dist[v] != INF)
{
printWay(v);
}
cout.println();
}
cin.close();
cout.close();
}
private void run() throws IOException
{
readData();
dejkstra(start);
printData();
cin.close();
cout.close();
}
public static void main(String[] args) throws IOException
{
Dex solution = new Dex();
solution.run();
}
}
Я попыталась сделать конвертер, чтоб из данной матрицы смежности получить эти данные:
Код:
//Find nodes and edges
//ordM - is entered by user
int rebro = 0;
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix.length; j++)
{
if(matrix[i][j] == 1 )
rebro +=1;
}
}
dArea.setText(new String(matrix.length + " "));
dArea.append(new String(rebro/2 + " "));
dArea.append(new String(ordM));
dArea.append(new String("\n"));
for (int j = 0; j < matrix.length; j++) {
for (int i = 0; i <= j; i++) {
if(matrix[i][j] == 1 )
{
dArea.append(new String((i+1) + " " + (j+1) + " " + 1));
dArea.append(new String("\n"));
}
}
}
Но выводит он корректно только если точка старта 1, т. к. проверяет в матрице треугольник по диагонали. (матрица в задаче всегда симметрична по диагонали).
Подскажите, пожалуйста, можно ли как-то исправить "конвертер" или может использовать другой алгоритм для поиска минимального пути? И как посоветуете искать максимальный путь?