Prim's Algorithm is similar to Dijkstra's with the difference that \(d[v]\) is the minimum between current value and \(w(v*, v)\) instead of \(d[v^*] + w(v^*, v)\) .
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
wD<:EQZU&2
Before
Front
Back
Prim's Algorithm is similar to Dijkstra's with the difference that \(d[v]\) is the minimum between current value and \(w(v*, v)\) instead of \(d[v^*] + w(v^*, v)\) .
Dijkstra's find the shortest distance to each vertex, thus it tracks the total.
Prim's needs to build the MST, thus it only cares about which vertex to choose next to find a (cheapest) safe-edge.
Prim's needs to build the MST, thus it only cares about which vertex to choose next to find a (cheapest) safe-edge.
After
Front
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.
Back
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.
Dijkstra's find the shortest distance to each vertex, thus it tracks the total. distance
Prim's needs to build the MST. As in the loop we add vertex \(v\) to the MST, we now want to know the new least distance to the MST for each node.
Prim's needs to build the MST. As in the loop we add vertex \(v\) to the MST, we now want to know the new least distance to the MST for each node.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <b>Prim's Algorithm</b> is similar to {{c1:: Dijkstra's}} with the difference that {{c1:: \(d[v] |
<b>Prim's Algorithm</b> is similar to {{c1:: Dijkstra's}} with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}. |
| Extra | Dijkstra's find the shortest distance to each vertex, thus it tracks the total.<br><br>Prim's needs to build the MST |
Dijkstra's find the shortest distance to each vertex, thus it tracks the total. distance<br><br>Prim's needs to build the MST. As in the loop we add vertex \(v\) to the MST, we now want to know the new least distance to the MST for each node. |