Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Вопрос-Ответ Новый топик    Ответить
 очень нужна помощь c java начинающему  [new]
olesya.
Member

Откуда:
Сообщений: 2
Здравствуйте!
Очень нужно разобраться с заданием по java.
У меня есть файл, в приложении. Это список, где через запятую расположены коды городов и вес расстояния между ними.
Город, город, вес
Мне нужно ответить на несколько вопросов по файлу. (есть также файл с расшифровкой номеров названиями городов).
Например, между какими двумя городами наибольшее количество кратчайших путей; сколько кратчайших путей между городом таким-то и таким-то; какие города находятся дальше всего от такого-то города и т.д.
В задании сказано, что нужно применять алгоритм дейкстры. При этом нужно ответить на вопросы без учета кратчайших путей, которые объединяют города напрямую. То есть найти нужно кратчайшие рейсы, но с пересадками)
Казалось бы, всё ясно. Но мне нет(((
Я правильно понимаю, что мне надо представить массив в виде матрицы смежности, а затем на ней запустить алгоритм?
Что использовать, чтобы отсеять прямые маршруты?
И более того, в задаче даже приводятся пример кода, но у меня, видимо, с класспас проблема. Файл находится в той же директории, что и программа, но я не могу извлечь данные.
Хотя бы помогите с тем, каким кодом извлекать данные из такого массива.
Это код, который не открывает файл.
import java.io.*;
import java.util.Scanner;
import java.util.*;
class Assignment2
{
static int N= 500;
static double [][] edges = new double[N][N];
static TreeMap <Integer,String> cityNames = new TreeMap
 <Integer,String>();
 static ArrayList<String> convert(ArrayList<Integer> m)
 {
 ArrayList<String> z= new ArrayList<String>();
 for (Integer i:m)
 z.add(cityNames.get(i));
  return z;
 }
 static HashSet<ArrayList<String>> convert
 (HashSet<ArrayList<Integer>> paths)
 {
 HashSet <ArrayList <String>> k= new HashSet
 <ArrayList<String>>();
 for (ArrayList <Integer> p:paths)
 k.add(convert(p));
  return k;
 }
 public static void main(String[] args) throws Exception
 {
 for(int i=0;i<N;i++)
 for(int j=0;j<N;j++)
 edges[i][j]=0.0;
 Scanner s = new Scanner(new FileReader("randomGraph"));
 String z =s.nextLine();
 while (s.hasNext())
 {
 z =s.nextLine();
 String[] results = z.split(",");
 edges[Integer.parseInt(results[0])]
 [Integer.parseInt(results[1])]=1.0;
 edges[Integer.parseInt(results[1])]
 [Integer.parseInt(results[0])]=1.0;
 }
 s = new Scanner(new FileReader("cities"));
 z =s.nextLine();
 while (s.hasNext())
 {
 z =s.nextLine();
 String[] results = z.split(",");
 cityNames.put(Integer.parseInt(results[0]),
 results[1]);
 }
 graph G= new graph(edges);
 int st =Integer.parseInt(args[0]);
 int fin = Integer.parseInt(args[1]);
  System.out.println("Shortest path from " +
  cityNames.get(st) + " to " +
 cityNames.get(fin) + " is" +
 convert(G.shortestPaths(st,fin)));
 }
}

Модератор: Тэг src облегчает понимание кода.


К сообщению приложен файл (randomGraph.csv - 17Kb) cкачать
15 мар 19, 01:16    [21833150]     Ответить | Цитировать Сообщить модератору
 Re: очень нужна помощь c java начинающему  [new]
Valentin Kolesnikov
Member

Откуда:
Сообщений: 3162
olesya.,

Добрый день,

Похожая задача с примерами решений.

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/description/

Хорошего Вам дня!
15 мар 19, 05:58    [21833204]     Ответить | Цитировать Сообщить модератору
 Re: очень нужна помощь c java начинающему  [new]
olesya.
Member

Откуда:
Сообщений: 2
Valentin Kolesnikov,

спасибо за помощь, но в примере из вашей ссылки n - число вершин. Это все же не очень подходит, в моем случае дан вес ребра.
15 мар 19, 18:07    [21834178]     Ответить | Цитировать Сообщить модератору
Все форумы / Вопрос-Ответ Ответить