Поиск кратчайшего пути с условием

29.01.2013, 23:59. Показов 1440. Ответов 0

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

Дан ориентированный граф, задаётся количеством вершин - m и рёбер- n, списком рёбер.
Необходимо найти кратчайший путь из вершины t в s, с условием: если их несколько вывести тот путь в котором максимальное ребро минимально. Вывести максимальное ребро входящее в путь.
Например:
3 3
1 2 1
2 3 2
1 3 3
1 3
Вывод: 1 2 3
2
Пояснение: в пути 1-2-3 максимальное ребро -2, а в пути 1-3 - максимальное ребро 3.
Как ни пробовал для всех случаев не получается написать правильное решение.
м.б. поможет - обычный алгоритм Дейкстры.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const
  maxn = 100;
  infinity = maxlongint;
var
  i,j,u,v,n,m,c,min,s,t:longint;
  e,w:array[1..maxn,1..maxn]of longint;
  ne,use,p,d:array[1..maxn]of longint;
begin
  read(n,m,t,s);
  for i:=1 to m do begin
    read(u,v,c);
    inc(ne[v]); e[v,ne[v]]:=u;
    w[v,u]:=c;
  end;
  for i:=1 to n do d[i]:=infinity;
  d[s]:=0;
  for i:=1 to n do begin
    min:=infinity;
    for j:=1 to n do if (use[j]=0)and(d[j]<min) then begin
      min:=d[j]; u:=j;
    end;
    use[u]:=1;
    for j:=1 to ne[u] do begin
      v:=e[u,j];
      if d[v]>d[u]+w[u,v] then begin
        d[v]:=d[u]+w[u,v]; p[v]:=u;
      end;
    end;
  end;
  writeln(d[t]);
  u:=t; write(u);
  while u<>s do begin
    u:=p[u]; write(' ',u);
  end;
end.

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

29.01.2013, 23:59

Ответы с готовыми решениями:

Поиск кратчайшего пути (алгоритм Дейкстры) с наименьшим максимальным ребром
Есть классическая реализация Дейкстры, пытаюсь добавить условие: если есть несколько кратчайших путей, то вывести минимальную из...

Поиск кратчайшего пути от точка 1 до точки n, пройдя все остальные точки
в общем такая задача, есть n точек. и расстояние от каждой точки до других. как найти минимальное расстояние от точки 1 до точки n. можете...

Нахождение кратчайшего пути до цели в лабиринте
Допустим у нас есть лабиринт,в котором бегают какие-нибудь существа. Есть ли возможность, чтобы они доходили до определенной точки...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

29.01.2013, 23:59

Помогаю со студенческими работами здесь

Поиск кратчайшего пути в алгоритме флойда! (На графах)
Алгоритм флойда! Нужно найти поиск кратчайшего пути в графе Program Algoritm_Floyda; Const NN=100; Type Graph = array of...

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового алгоритма и алгоритма Дейксты в плане...

Поиск кратчайшего пути
В одном массиве даны все возможные комбинации чисел (0,1,2,3,4). Представляют собой города. В другом массиве - расстояния между этими...

Поиск кратчайшего пути
Нужно найти кратчайший путь в графе не используя эффективных методов, т.е. полным перебором путей. Обшарил можно ресурсов, но толком ничего...

Поиск кратчайшего пути
Саша и Маша путешествуют вдоль оси Ох на которой есть (неизвестное кол-во) достопримечательностей в точках с координатами х1 , х2 , ... , и...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .	Команды "Заполнить" и "Очистить" на форме документа Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа разработанного в конфигурации КА2. В качестве источника данных указан регистр накопления, в который записываются данные о. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip

Наверх