Küzester Weg bei Graphen mit gleichen Kantengewichtungen

[Satheno]

Hallo zusammen,

ich habe folgendes Problem: Ich habe einen Graphen gegeben mit beliebig vielen, aber endlich vielen, Knoten und Kanten, welche diese verbinden, gegeben. Die Kanten haben alle, egal welche Knoten sie verbinden, als Kosten 1. Hat jemand einen Ansatz wie ein Algorithmus aussehen kann der mir da den kürzesten Weg zwischen 2 Punkten zurückgibt?
Ich muss das ganze in Python programmieren und hab mir bereits eine Adjazenzmatrix erstellt, also ich weiß welcher Knoten mit welchem verbunden ist, aber ich komme partout nicht auf einen möglichst einfachen Algorithmus.

Ich danke allen schonmal für die Antworten

 

[NeoExacun]

Dijkstra

 

[ZuseZ3]

Prim

 

[kuddlmuddl]

A*

 

[Kanibal]

http://alda.iwr.uni-heidelberg.de/i...in_ungewichteten_Graphen_mittels_Breitensuche

 

[pfd]

Wie NeoExacun bereits geschrieben hat ist die Implementierung des Algorithmus von Dijkstra eine mögliche Lösung.
Wenn man in Google nach "dijkstra filetypedf" sucht bekommt man sehr gute Ergebnisse, z.B.:

• Link 1
• Link 2
• Link 3

Oder bei rosettacode.

@ZuseZ3: Mittels Algorithmus von Prim (den, den ich kenne) wird nur der minimale Spannbaum ermittelt.

 

[Kanibal]

Dijkstra ist aber bei identischen Kantengewichten (entspricht einem ungewichteten Graphen) aufwendiger und langsamer als eine Breitensuche.

 

[NeoExacun]

Das ist korrekt. Bei ungewichteten Kanten dürfte die Breitensuche das Effizienteste sein.

 

[Satheno]

Ok, ich danke euch allen für die Antworten. Ich werd mich mal ransetzen und rumprobieren

 

[titanskin]

Breitensuche/Tiefensuche wird am schnellsten laufen. Bitte vergesse die Optimierung der Abbtuchsbedingung nicht.
Breitensuche hat sogar dann den Vorteil, dass es in O (Pfadlänge) bestimmt terminiert. Bei Tiefensuche kann ich nichts derart offensichtliches finden.