Citat:
Ursprungligen postat av mp-jby
Är jag på rätt spår? Känns som en väldigt långdragen och osmidig lösning.
Om du får rätt resultat så är du på rätt spår. Att hitta kortaste avståndet i grafer
är långdraget och osmidigt, eftersom man i princip måste köra på brute force för att vara säker.
Just i ditt fall, följandes algoritmen som den står på Wikipedia:
Citat:
1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
Kod:
Tentative distances:
A 0
B ∞
C ∞
G ∞
Citat:
2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
Kod:
Unvisited set:
B C G
Citat:
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
Kod:
Tentative distances:
A 0
B 6
C 8
G 2
Citat:
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
Kod:
Unvisited set:
B C G
Citat:
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
Nope.
Citat:
6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
Kod:
Tentative distances:
A 0
B 6
C 8
G 2
Kod:
Unvisited set:
B C G
Citat:
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
Kod:
Tentative distances:
A 0
B 6
C 3
G 2
Citat:
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
Citat:
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
Nope.
Citat:
6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
Kod:
Tentative distances:
A 0
B 6
C 3
G 2
Citat:
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
Kod:
Tentative distances:
A 0
B 6
C 3
G 2
Citat:
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
Citat:
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
Yes! För att ta reda på kortaste vägen behöver man nu bara följa de kortaste siffrorna baklänges från C. I det här fallet blir det C -> G -> A. Vänd på det och du har vägen A -> G -> C!
