Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Програмний засіб знаходження найкоротших шляхів в графі

Реферат Програмний засіб знаходження найкоротших шляхів в графі





шину не обраховують

} w=tn.aEdge [e] .Weight;// вага того ребра по якому ми можемо

піти

if (current_weight + w gt; best_weight)//є легші шляхи

{[v] ++;// шукаємо далі за списком куди можна піти;// і далі можна цю вершину не обраховують

} t;// чи потрібна пересадка для потрапляння в наступну

//вона потрібна якщо вершини належать різним транспортним мережам

if (tn.aVertex [v] .iGraph!=tn.aVertex [vv] .iGraph)

t=1;=0;

//є більш короткі шляхи

if (current_transfer + t gt; numericUpDownTransfer.Value)

{[v] ++;// шукаємо далі за списком куди можна піти;// і далі можна цю вершину не обраховують

}

//йти в цю вершіну_path.Push (vv);// покласти в стек вершіну_pathE.Push (e);// покласти в стек ребро

//йти в цю вершину

//перерахувати показателі_transfer +=t;// збільшимо кількість пересадок_weight +=w;// збільшимо вартість шляху

//перерахувати показники

//і так як ми пішли в вершину, то у нас тепер інша поточна і цикл

потрібно кінчати;

} (v == current_path.Peek ())//якщо з вершини йти далі нікуди

{(v == s) current_path.Pop ();// робимо останній крок назад (v == s) break;// саме останній крок назадe;// за яким ребру дійшли до цієї вершини

//узна? му його по вершині стека, тому в стеку щось точно є=current_pathE.Peek (); v1=tn.aEdge [e] .srcVertex;// початок ребра по якому прішліv2=tn.aEdge [e] .destVertex;// кінець ребра по якому прішліt;// чи потрібна була пересадка для потрапляння в цю вершину

//вона потрібна якщо вершини належать різним транспортним мережам

if (tn.aVertex [v1] .iGraph!=tn.aVertex [v2] .iGraph)

t=1;=0; w=tn.aEdge [e] .Weight;// вага ребра по якому ми прийшли в цю

вершини

//перерахувати показники

//зменшити кількість пересадок, тому ми збираємося робити крок

назад_transfer -=t;

//зменшити вагу поточного шляху, тому ми збираємося робити крок назад_weight -=w;

//перерахувати показники

//вийти з цієї вершіни_path.Pop ();// робимо крок назад_pathE.Pop ();// робимо крок назад

//вийти з цієї вершини

//і так як ми з цієї вершини пішли, то лічильник ребер для неї

обнуляється [v]=- 1;

}

//якщо ж ми не дійшли ещ? до фінальної вершини

}

}

}

//рекурсивний пошук в глубінуvoid rdfs (int s, int v, int e, int finish)

{

//чи можна йти в цю вершину

if (current_path.Contains (v) == true) return;// ми в ній вже були (tn.aVertex [v] .Enabled == false) return;// в неї йти не можна (e!=- 1) (tn.aEdge [e] .Enabled == false) return;// по цьому ребру йти не можна

//чи можна йти в цю вершину

//чи потрібно йти в цю вершінуw;// вага того ребра, по якому йдемо

if (e!=- 1)=tn.aEdge [e] .Weight;=0; (current_weight + w gt; best_weight) return;// є легші шляхи

int t;// чи потрібна пересадка (e!=- 1)

{(tn.aVertex [s] .iGraph!=tn.aVertex [v] .iGraph)=1;=0;

}=0; (current_transfer + t gt; numericUpDownTransfer.Value)//є більш

короткі шляхи

return;

//чи потрібно йти в цю вершину

//йти в цю вершіну_path.Push (v);

if (e!=- 1) current_pathE.Push (e);

//йти в цю вершину

//перерахувати показники

current_transfer +=t; _weight +=w;

//перерахувати показники

//якщо дійшли (v == finish)

{(current_weight lt; best_weight)

{_ weight=current_weight; _path=new Stack lt; int gt; (current_path); _ pathE=new Stack lt; int gt; (current_pathE);

}

}

//якщо дійшли

//йти з цієї вершини в усі інші по черзі

foreach (int iE in tn.aVertex [v] .iEdge)

{vv;// один з варіантів, куди можна піти

if (tn.aEdge [iE] .srcVertex == v)=tn.aEdge [iE] .destVertex;=tn.aEdge [iE] .srcVertex; (v, vv, iE, finish);

}

//йти з цієї вершини в усі інші по черзі

//перерахувати показателі_transfer -=t; _weight -=w;

//перерахувати показники

//вийти з цієї вершини

current_path.Pop (); (e!=- 1) current_pathE.Pop ();

//вийти з цієї вершини

}




ДОДАТОК Ж


Функція пошуку оптимального шляху


private void buttonSearch_Click (object sender, EventArgs e)

{start=- 1;// стартова вершінаfinish=- 1;// кінцева вершина

//шукаємо стартову і кінцеву вершину (int i=0; i lt; tn.aVertex.Count; i ++)

{(tn.aVertex [i] .IsStart == true) start=i; (tn.aVertex [i] .IsFinish == true) finish=i;

}

//якщо хоча б одну не знайшли (start == - 1 || finish == ...


Назад | сторінка 23 з 24 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Пошук вершини в графі між двома заданими вершинами
  • Реферат на тему: Анексія Криму, як можна вірішіті Конфлікт України с Россией чі можна его ві ...
  • Реферат на тему: Шизофренія. Лікувати, не можна хворіти
  • Реферат на тему: Коли працювати можна менше ...
  • Реферат на тему: Спостереження за роботою листоноші і міркування про поліпшення цієї роботи ...