GRAFOS – RIO GRANDE DO SUL

GRAFOS – RIO GRANDE DO SUL

            CIÊNCIA DA COMPUTAÇÃO – 6º SEMESTRE        [pic 2]

São Paulo, 2013

---

Sumário

1.        INTRODUÇÃO        7

2.        MATRIZ E LISTA DE ADJACÊNCIA        7

3.        MATRIZ AUXILIARES PARA O SISTEMA        8

4.        CÓDIGO        9

5.        TELA DE EXECUÇÃO        14

6.        GRAFO (RS)        15

7.        CONCLUSÃO        15

---

1. INTRODUÇÃO

Este trabalho consiste em implementar o algoritmo de caminho mínimo de Dijkstra para a representação do Grafo (Rio Grande do Sul) escolhendo no mínimo 10 cidades, e representando as ligações através da malha rodoviária.

1. MATRIZ E LISTA DE ADJACÊNCIA

Matriz:

[pic 3]

Lista:

[pic 4]

1. MATRIZ AUXILIARES PARA O SISTEMA

[pic 5]

[pic 6]

[pic 7]

[pic 8]

1. CÓDIGO

using System;

using System.Windows.Forms;

using System.Xml;

using System.Collections;

using System.Collections.Generic;

namespace GrafoRS

{

    public partial class Grafo : Form

    {

        ArrayList Origens;

        ArrayList Destinos;

        ArrayList Distancias;

        String[,] Adj = new String[11,11];

        String[,] AdjDist = new String[11, 11];

        String[,] d = new String[10, 2];

        String[,] pi = new String[10, 2];

        List<Resultado> lstRes;

        public Grafo()

        {

            InitializeComponent();

        }

        private void btnRota_Click(object sender, EventArgs e)

        {

            Djikstra(cbOrigem.Text);

            CarregarResultado();

            String Origem = "";

            String Destino = cbDestino.Text;

            List<String> Caminho = new List<string>();

            Caminho.Add(Destino);

            int pos = 0;

            while (Origem != cbOrigem.Text)

            {

                if (lstRes[pos].Cidade == Destino)

                {

                    if (lstRes[pos].Cidade == cbOrigem.Text)

                        Origem = lstRes[pos].Cidade;

                    else

                    {

                        Caminho.Add(lstRes[pos].PI);

                        Destino = lstRes[pos].PI;

                        pos = 0;

                    }

                }

                else

                pos++;

            }

            for (int i = Caminho.Count-1; i >= 0; i--)

            {

                lbcCaminho.Items.Add(Caminho[i]);

            };

        }

        public void CarregarResultado()

        {

            Resultado res;

            lstRes = new List<Resultado>();

            for (int i = 0; i < Origens.Count; i++)

            {

                res = new Resultado(d[i, 0].ToString(), d[i, 1].ToString(), pi[i, 1].ToString());

                lstRes.Add(res);

            }

           

            gcResultados.DataSource = lstRes;

        }

        private void Djikstra(String origem)

        {

            String s = origem;

            List<String> S = new List<string>(); //Solução