Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Apuntes

Summary of Chapter 3

jakubburger Decision Inglés 1 página

Contenido del apunte (1)

Página 1

1 Kruskal's algorithm and Prim's algorithm can be used to find a minimum spanning tree, but they take different approaches.

2 To use Kruskal's algorithm, you sort the arcs into ascending order of weight and use the arc of least weight to start the tree. You then add arcs in order of ascending weight, unless an arc would form a cycle, in which case it is rejected.

3 To use Prim's algorithm, you choose any vertex to start the tree. You then select an arc of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree. You repeat this until all vertices are connected.

4 Prim's algorithm can be applied to a distance matrix. You choose any vertex to start the tree. You delete the row in the matrix for the chosen vertex and number the column in the matrix for the chose vertex. You ring the lowest undeleted entry in the labelled columns, which becomes the next vertex. You repeat this until all rows are deleted.

5 You can use Dijkstra's algorithm to find the shortest path between two vertices in a network.

6 The start vertex is given the final value 0. Every vertex that is directly connected to the start vertex is given a working value

final value at start + weight of arc.

Select the smallest working value. This is the final value for that vertex. Repeat until the destination vertex receives its final label. Find the shortest path by tracing back from destination to start. Include an arc AB on the route if B is already on the route and

final label B - final label A = weight of arc AB

7 Each vertex is replaced by a box

Summary of Chapter 3

Page 1

Información

Descripción
(Chapter 3: Algorithms on networks) Decision Apunte sobre Summary of Chapter 3, creado por jakubburger el 11/04/2013.
Creado por
jakubburger · abr 2013
Actualizado
19 feb 2016
Visitas
83
Etiquetas
chapter 3: algorithms on networksdecision
Valoración

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?