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

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





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

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

//генеруємо для черги чергове напрямок руху

qV.Enqueue (new Stack lt; int gt; (current_path));

//генеруємо для черги чергове напрямок руху

qE.Enqueue (new Stack lt; int gt; (current_pathE));

//генеруємо для черги чергове напрямок двіженія.Enqueue (current_weight);

//генеруємо для черги чергове напрямок двіженія.Enqueue (current_transfer);

//вернуться_path.Pop ();// дістати з стека вершіну_pathE.Pop ();// дістати з стека ребро

//повернутися

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

//повернутися і персчітать показники

}

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

}

}

}

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

{

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

збігається з фінальною (s == finish)

{// звичайно це рідкісний випадок, але тим не менш

best_path.Push (s) ;;

} v;// номер поточної вершини

//в цьому всмпомогательном масиві ми пам'ятатимемо індекс ребра,

по якому ходили з цієї

вершини востаннє [] d=new int [tn.aVertex.Count];

//ні з однієї вершини нікуди ещ? не ходили

for (int i=0; i lt; tn.aVertex.Count; i ++) d [i]=- 1;

current_path.Push (s);// в стеку лежить шлях, а шлях ми починаємо зі

стартовою вершини (current_path.Count!=0)//поки ми не переглянемо всі можливі

шляху

{= current_path.Peek ();// узна? м номер поточної вершини (v == finish)

{

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

if (current_weight lt; best_weight)

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

}

//якщо дошлі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;

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

}

{

//якщо ж ми не дійшли ще до фінальної вершини [v] ++;// шукаємо далі за списком куди можна піти

while (d [v] lt; tn.aVertex [v] .iEdge.Count)

{vv;// в цю вершину є ребро з текущейe=tn.aVertex [v] .iEdge [d [v]];// от якраз це ребро і йде з

поточної

if (tn.aEdge [e] .srcVertex == v)=tn.aEdge [e] .destVertex;=tn.aEdge [e] .srcVertex;

if (current_path.Contains (vv) == true)//туди йти не можна, ми там вже

були

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

} (tn.aVertex [vv] .Enabled == false)//в неї йти не можна, вона

заблокована

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

}

//по цьому ребру йти не можна, воно заблоковане

if (tn.aEdge [e] .Enabled == false)

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


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





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

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