Вече има примерен вход и примерен изход на всички задачи от темата "Advanced Graph Algorithms", както и картинки, за по-лесна ориентация + насоки за решение (hints).

Имайте предвид, че това е една от най-важните и най-трудните теми в курса и поне една от задачите на изпита ще са върху материала от тази тема.

Наков

Здравейте :)

Темата наистина е тегавичка, поне за сравнително начинаещ като мен. От лекциите почти всичко ми е ясно, но като седна да пиша става весело и още се опитвам да отлепя от първата задача на лаб-а.

Алгоритъма на Крускал по заданието изглежда горе-долу така, с TODO-тата както ги разбрах аз:

var spanningTree = new List<Edge>();
edges.Sort();
foreach (Edge edge in edges)
{
    int rootStartNode = FindRoot(edge.StartNode, parent);
    int rootEndNode = FindRoot(edge.EndNode, parent);
    if (rootStartNode != rootEndNode)
    {
        spanningTree.Add(edge);
        parent[edge.EndNode] = edge.StartNode;
    }
}

с допълнение сортирането на входните ребра на графа на ред 2. Без него получавам:

Minimum spanning forest weight: 53
(0 3) -> 9
(0 5) -> 4
(0 8) -> 5
(1 4) -> 8
(1 7) -> 7
(2 6) -> 12
(3 6) -> 8

а с него:

Minimum spanning forest weight: 82
(3 5) -> 2
(0 5) -> 4
(0 8) -> 5
(1 7) -> 7
(6 8) -> 7
(1 4) -> 8
(3 6) -> 8
(0 3) -> 9
(2 6) -> 12
(3 8) -> 20

в първия случай ребрата са правилния брой, но не са правилните, а във втория - разстоянията са ок, но има излишни ребра, и не мога да разбера къде е заровено кучето, дето се вика :D

Тук е целия клас.

Здравейте,

Имам неясноти по разбирането на условоието на първа задача от домашното. Най-вече ме обърка този Hint накрая. Според мен ако се действа по тази схема изобщо няма да има гаранция дали ще се изпълни условието да се свържат колкото се може повече клиенти. Пример:

Ако на диаграмата от първия пример за възел 2 е закачен възел А и реброто 2-А има тежест 8 например и предположим, че за А има навързани верижно още 100 ребра - А-B-C-D.... с тежест 1. Ако пуснем Прим, той ще предпочете най малкото ребро, което свързва свързаните до момента клиенти с нов клиен и ще спре преди да надхвърли лимита, т.е ще имаме същия изход като на примерната диграма и ще имаме присъединени 3 нови клиента. Ако тръгнем пък от 2-A-B-C ще можем да присъединим 13 нови клиента за цена 20. Подобна е ситуацията ако първоначално нямаме никакви връзки. Трябва да започнем или от случайно място, което ще доведе потенциално до грешен резултат или от възел който е край на най-малкото ребро, което пак може да е грешно (заради контрапример подобен на горния). Не съм убеден , че точно в този конкрете случай  "лакомия" подход ще работи.

Друго решение е да пуснем Prim от всеки свободен възел и да спираме когато се свържем към съществуващата мрежа(ако има такава). Но това съществено се различава като подход от упътването и не мисля, че такава е била идеята.

Освен това на последния пример изхода също не го разбирам много, защото мрежата е разцепена. Реално мрежата не трябва ли по дефиниция да е силно свързана част в графа. Няма логика според мен 5-6 да са отделени от останалата част.То ако ще е така по-добре с модификация на Kruskal и на всяка стъпка да се взима най-малкото ребро и единствено гледаме да не свързваме ребра с общ root.

Вие как приемате това условие?

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

Това домашно ми повдига много въпроси и на мене. Схванах че първа задача иска Прим, но както каза колегата Прим просто не дава оптимални резултати в някой ситуации, тогава излиза добрия въпрос DP ли да ползвам и да пиша коментари вътре че излизат различни резултати, защото DP вади по оптимални решения или да си оставя Прим алгоритъма. Или по добре поставен въпроса идеята на задачата да упражним Прим ли е или да я решим оптимално?
 

На 3та задача или по точно за Dijkstra алгоритъма ми излиза следния въпрос, понеже много се блъсках да опитам да го направя оптимално, ако използвам BinaryHeap за приоритетна опашка при намирането на по добър път към node, се иска да се преподреди опашката (предполагам с идеята че новия път може да го постави на по предна позиция за обхождане), но при положение че всички node-ове трябва да бъдат обходени така или иначе, няма ли този процес само да ни забави. При голяма опашка едно преподреждане изглежда като много по скъпа операция от операцията за презаписване на разстоянието. Сега като обмислям нещата може би самият въпрос е какво печелим от използването на приоритетна опашка за Dijkstra.

На задача 5 Shortest Paths with Negative Edges, най-късата дистанция не е ли [4 -> 9]: -58? Защото пътя от 4 до 3 е -5, което е по-малко от пътя от 0 до 3: -4.