Conversión de matriz a grafo y obtención de ruta optima
Enviado por crujitos • 14 de Noviembre de 2018 • Trabajo • 1.319 Palabras (6 Páginas) • 1.716 Visitas
Conversión de matriz a grafo y obtención de ruta optima
Matriz 1
Nodo | 1 | 2 | 3 |
1 | 0 | 15 | 25 |
2 | 15 | 0 | 10 |
3 | 25 | 10 | 0 |
[pic 1]
15
25 10
Primer recorrido
15[pic 2]
25 10
Del punto 1 al punto 2 se obtiene 15.
Del punto 2 al punto 3 se obtiene 10.
Del punto 3 al punto 1 se obtiene 25.
El resultado es 50.
Segundo recorrido
15[pic 3]
25 10
Del punto 1 al punto 3 se obtiene 25.
Del punto 3 al punto 2 se obtiene 10.
Del punto 2 al punto 1 se obtiene 15.
El resultado es 50.
Tercer recorrido[pic 4]
15
25 10
Del punto 2 al punto 1 se obtiene 15.
Del punto 1 al punto 3 se obtiene 25.
Del punto 3 al punto 2 se obtiene 10.
El resultado es 50.
Dentro de los tres recorridos analizados, los tres son el recorrido óptimo.
Matriz 2
Nodo | 1 | 2 | 3 | 4 |
1 | 0 | 10 | 20 | 30 |
2 | 10 | 0 | 40 | 50 |
3 | 20 | 40 | 0 | 60 |
4 | 30 | 50 | 60 | 0 |
[pic 5]
10
20 40
30
50
60
Primer recorrido[pic 6]
10
40
30
60
Del punto 1 al punto 2 se obtiene 10.
Del punto 2 al punto 3 se obtiene 40.
Del punto 3 al punto 4 se obtiene 60.
Del punto 4 al punto 1 se obtiene 30.
El resultado es 140.
Segundo recorrido[pic 7]
10
20
50
60
Del punto 1 al punto 2 se obtiene 10.
Del punto 2 al punto 4 se obtiene 50.
Del punto 4 al punto 3 se obtiene 60.
Del punto 3 al punto 1 se obtiene 20.
El resultado es 140.
Tercer recorrido[pic 8]
20 40
30
50
Del punto 1 al punto 4 se obtiene 30.
Del punto 4 al punto 2 se obtiene 50.
Del punto 2 al punto 3 se obtiene 40.
Del punto 3 al punto 1 se obtiene 20.
El resultado es 140.
Dentro de los tres recorridos analizados, los tres son el recorrido óptimo.
Matriz 3
Nodo | 1 | 2 | 3 | 4 | 5 |
1 | 0 | 10 | 30 | 50 | 80 |
2 | 10 | 0 | 55 | 95 | 105 |
3 | 30 | 55 | 0 | 120 | 155 |
4 | 50 | 95 | 120 | 0 | 200 |
5 | 80 | 105 | 155 | 200 | 0 |
[pic 9]
10
30 55
80 105 50
155 95 120
...