Dijsktra's Algorithm
FInding the shortest path
It is guarenteed to find us the best possible path, however it is relatively slow as it checks everything.
This is Dijkstra's Algorithm to find the shortest path from S to T through a network.
1. Label the start vertex, S, with the final label, 0.
2. Record a working value att every vertec, Y, that is ditectly connected to the vertex, x, that hs just recieved its
final label
1. Working value at Y = final value at X + weight of arc XY
2. If there is already a working value at Y, it is only replaced if the new value is smaller.
3. Once a vertex has a inal label it is not revisited and its working values are no longer considered
4. Look at the working values at all vertices without final labels. Select the smallest working value. This now
becomes the final label at the vertex. (If two vetticees have the smallest working value either may be given i
final label first).
5. Repeat steps 2 and 3 until the desitnation vertex , T, recieves its final label.
,6. To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB
whenever final label of B - final label of A = weight of arc AB.
,Algorithms - Bin Packing
The bin pakcing uses sorting of numbers and is a massive simplification of a real problem.
FInding the shortest path
It is guarenteed to find us the best possible path, however it is relatively slow as it checks everything.
This is Dijkstra's Algorithm to find the shortest path from S to T through a network.
1. Label the start vertex, S, with the final label, 0.
2. Record a working value att every vertec, Y, that is ditectly connected to the vertex, x, that hs just recieved its
final label
1. Working value at Y = final value at X + weight of arc XY
2. If there is already a working value at Y, it is only replaced if the new value is smaller.
3. Once a vertex has a inal label it is not revisited and its working values are no longer considered
4. Look at the working values at all vertices without final labels. Select the smallest working value. This now
becomes the final label at the vertex. (If two vetticees have the smallest working value either may be given i
final label first).
5. Repeat steps 2 and 3 until the desitnation vertex , T, recieves its final label.
,6. To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB
whenever final label of B - final label of A = weight of arc AB.
,Algorithms - Bin Packing
The bin pakcing uses sorting of numbers and is a massive simplification of a real problem.
