In dieser Woche setzen wir die Untersuchung von Algorithmen zur Graphenzerlegung fort, aber jetzt für gerichtete Graphen.

In diesem Modul werden Sie Algorithmen zum Finden kürzester Wege in Graphen studieren. Diese Algorithmen haben viele Anwendungen. Wenn Sie eine Navigations-App auf Ihrem Smartphone starten, wie z.B. Google Maps oder Yandex.Navi, verwendet sie diese Algorithmen, um die schnellste Route von der Arbeit nach Hause, von zu Hause zur Schule usw. zu finden. Wenn Sie nach Flugtickets suchen, werden diese Algorithmen verwendet, um eine Route mit der geringsten Anzahl von Umstiegen zu finden. Unerwarteterweise können diese Algorithmen auch verwendet werden, um den optimalen Weg für den Währungsumtausch zu finden, wodurch Sie manchmal einen großen Gewinn erzielen können! Wir werden all diese Anwendungen behandeln und Sie werden die Breadth-First Search, den Dijkstra-Algorithmus und den Bellman-Ford-Algorithmus kennenlernen. Diese Algorithmen sind effizient und legen den Grundstein für noch effizientere Algorithmen, die Sie im Shortest Paths Capstone Project erlernen und implementieren werden, um die besten Routen auf realen Karten von Städten und Ländern zu finden und Entfernungen zwischen Personen in sozialen Netzwerken zu ermitteln. Am Ende werden Sie in der Lage sein, effizient kürzeste Wege in jedem beliebigen Graphen zu finden. Diese Woche werden wir uns mit dem Breadth-First Search Algorithmus beschäftigen.

Diese Woche setzen wir das Studium der kürzesten Wege in Graphen fort. Sie lernen den Dijkstra-Algorithmus kennen, der angewendet werden kann, um den kürzesten Weg von der Arbeit nach Hause zu finden. Außerdem lernen Sie den Algorithmus von Bellman-Ford kennen, mit dem Sie unerwartet den optimalen Weg für den Währungsumtausch finden können. Am Ende werden Sie in der Lage sein, effizient kürzeste Wege in einem beliebigen Graphen zu finden.

In diesem Modul untersuchen wir das Problem des minimalen Spannbaums. Wir werden zwei elegante gierige Algorithmen für dieses Problem behandeln: der erste stammt von Kruskal und verwendet die Datenstruktur disjunkte Mengen, der zweite stammt von Prim und verwendet die Datenstruktur Prioritätswarteschlange. In der Programmieraufgabe für dieses Modul werden Sie einen optimalen Weg zum Bau von Straßen zwischen Städten und einen optimalen Weg zur Partitionierung einer gegebenen Menge von Objekten in Cluster (ein grundlegendes Problem im Data Mining) berechnen.

In diesem Modul lernen Sie fortgeschrittene Algorithmen für kürzeste Wege kennen, die in der Praxis 1000-mal (bis zu 25000-mal) schneller arbeiten als der klassische Dijkstra-Algorithmus auf realen Straßennetzen und Graphen sozialer Netzwerke. Sie werden an einem Programmierprojekt arbeiten, das auf diesen Algorithmen basiert. Sie werden die kürzesten Wege auf den realen Karten von Teilen der USA und die kürzesten Wege zwischen den Menschen in den sozialen Netzwerken finden. Wir ermutigen Sie nicht nur, die Ideen aus den Vorlesungen dieses Moduls in Ihren Implementierungen zu verwenden, sondern auch eigene Ideen zur Beschleunigung des Algorithmus zu entwickeln! Wir ermutigen Sie, sich in den Foren zu messen, um zu sehen, wer die schnellste Implementierung hat :)