Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: directed weighted graph

Sortuj według:

Ogranicz wyniki do:

Algorytm wyznaczania połączenia komunikacyjnego o minimalnym czasie przejazdu z dodatkową minimalizacją kosztu przejazdu

Widuch J., Wicher D.

Studia Informatica

2012

Vol. 33, nr 4

59--79

Wyznaczanie tras przejazdu jest jednym z badanych problemów transportowych. W niniejszej pracy przedstawiono problem wyznaczania połączeń w sieciach komunikacyjnych, którego celem jest wyznaczenie połączenia o minimalnym czasie przejazdu dla zadanej pary przystanków początkowego i końcowego oraz godziny rozpoczęcia podróży. Jeżeli istnieje więcej połączeń o minimalnym czasie przejazdu, to spośród nich należy wyznaczyć połączenie o minimalnym koszcie przejazdu. W pracy zaprezentowano algorytm umożliwiający rozwiązanie badanego problemu. Zaprezentowano także przykładowe wyniki przeprowadzonych badań eksperymentalnych z użyciem rzeczywistej sieci komunikacyjnej.

The routing problem is one of the studied transportation problems. In the paper the communication networks routing problem is presented, in which the goal is to find a route from the start stop to the final stop minimizing the time of travel, where the time of starting travel at the start stop is given. If there are more routes with minimal the time of travel, among them the route with minimal the cost of travel should be determined. In the paper the algorithm for solving the communication networks routing problem is presented. Apart from that a sample results of experimental tests using the real communication network are presented.

A Label Correcting Algorithm for the Bus Routing Problem

Widuch J.

Fundamenta Informaticae

2012

Vol. 118, nr 3

305-326

This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.

Algorytm dewiacyjny dla problemu wyznaczania K najkrótszych ścieżek

Widuch J., Szołtysek M.

Studia Informatica

2011

Vol. 32, nr 1A

55-77

Jednym z badanych problemów teorii grafów jest problem wyznaczenia najkrótszej ścieżki. Rozszerzeniem tego problemu jest problem wyznaczenia K (K > 1) najkrótszych ścieżek. Badane są dwa warianty tego problemu. W pierwszym dopuszcza się wyznaczenie ścieżek zawierających cykle, a w drugim są wyznaczane wyłącznie ścieżki acykliczne. W pracy został przedstawiony algorytm dewiacyjny, umożliwiający wyznaczenie K najkrótszych ścieżek, które mogą zawierać cykle.

One of the studied problems of the graph theory is the shortest path problem. An extension of this problem is the problem of finding K (K > 1) shortest paths. Two variants of this problem are studied. In the first case path containing cycles are allowed, and in the second are determined only loopless paths. In the paper a deviation algorithm for solving K shortest paths, which may contain cycles is shown.

A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors

Nepomniaschaya A.S., Dvoskina M.A.

Fundamenta Informaticae

2000

Vol. 43, Nr 1-4

227-243

In this paper we propose a natural straight forward implementation of Dijkstra's shortest path algorithm on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). In addition, we show how to extend this implementation for restoring the shortest path from the source vertex to a given vertex. These algorithms of implementation are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated.