Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.01.2017, 20:21   #1
VallMorgan
Новичок
Джуниор
 
Регистрация: 09.01.2017
Сообщений: 1
По умолчанию Поиск минимального и максимального пути в графе

Необходимо найти минимальный и максимальный пути от данной вершины (ее указывает пользователь) до всех остальных вершин в графе.

На входе имеется файл с матрицей смежности, например:
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, т. к. проверяет в матрице треугольник по диагонали. (матрица в задаче всегда симметрична по диагонали).

Подскажите, пожалуйста, можно ли как-то исправить "конвертер" или может использовать другой алгоритм для поиска минимального пути? И как посоветуете искать максимальный путь?
VallMorgan вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск кратчайшего пути в графе zokwild Помощь студентам 0 30.11.2012 18:22
Поиск максимального паросочетания в графе Begemotik_# Помощь студентам 0 15.05.2012 06:55
Поиск кратчайшего пути в графе BaceK Помощь студентам 0 18.12.2011 11:49
Поиск минимального и максимального пути в графе!!!! OZZY_91 Помощь студентам 1 18.11.2009 13:20