none
Algoritmo dijkstra tabela de custos. RRS feed

  • Pergunta

  • Eu tenho esse algoritmo que achei na internet de dijkstra, mas ele não está executando da maneira correta, o certo era passar o vertice x,y para ele e somar os custos dos vertices e dizer qual ele passou tipo, a,b,d,f.

    Exemplo essa imagem abaixo: onde está vazio é 0 onde possui dados é o custo.

     

    INTERNET

    BACKBONE

    FIREWALL

    SRV_DADOS

    SRV_DADOS_BK

    CLI_01

    CLI_02

    INTERNET

     

    1

     

     

     

     

     

    BACKBONE

    1

     

    2

     

     

     

     

    FIREWALL

     

     

     

    5

     

     

     

    SRV_DADOS

     

     

     

     

    4

    11

    9

    SRV_DADOS_BK

     

     

     

    4

     

    10

    8

    CLI_01

     

     

     

    11

    10

     

    12

    CLI_02

     

     

     

    9

    8

    12

     

     





























































    namespace ConsoleApp1
    {
        class Dijkstra
        {
    
            private static void EscreveDistancia(int[] distancia, int contaVertice)
            {
                Console.WriteLine("Vertice  Distância");
    
                for (int i = 0; i < contaVertice; ++i)
                    Console.WriteLine("{0}\t    {1}", i, distancia[i]);
            }
            private static int DistanciaMinima(int[] distancia, bool[] menorCaminho, int contaVertice)
            {
                int Menor = int.MaxValue;
                int retornaMenorIndice = 0;
    
                for (int v = 0; v < contaVertice; ++v)
                {
                    if (menorCaminho[v] == false && distancia[v] <= Menor)
                    {
                        Menor = distancia[v];
                        retornaMenorIndice = v;
                    }
                }
    
                return retornaMenorIndice;
            }      
            public static void Principal(int[,] arrayGrafico, int raiz, int contaVertice)
            {
                int[] distancia = new int[contaVertice];
                bool[] menorCaminho = new bool[contaVertice];
    
                for (int i = 0; i < contaVertice; ++i)
                {
                    distancia[i] = int.MaxValue;
                    menorCaminho[i] = false;
                }
    
                distancia[raiz] = 0;
    
                for (int conta = 0; conta < contaVertice - 1; ++conta)
                {
                    int u = DistanciaMinima(distancia, menorCaminho, contaVertice);
                    menorCaminho[u] = true;
    
                    for (int v = 0; v < contaVertice; ++v)
                        if (!menorCaminho[v] && Convert.ToBoolean(arrayGrafico[u, v]) && distancia[u] != int.MaxValue && distancia[u] + arrayGrafico[u, v] < distancia[v])
                            distancia[v] = distancia[u] + arrayGrafico[u, v];
                }
    
                EscreveDistancia(distancia, contaVertice);
            }
            static void Main(string[] args)
            {
                int[,] arrayGrafico =  {
                             { 0, 1, 0, 0, 0, 0, 0},
                             { 1, 0, 2, 0, 0, 0, 0},
                             { 0, 0, 0, 5, 0, 0, 0},
                             { 0, 0, 0, 0, 4, 11, 9},
                             { 0, 0, 0, 4, 0, 10, 8},
                             { 0, 0, 0, 11, 10, 0, 12},
                             { 0, 0, 0, 9, 8, 12, 0}
                };
                Principal(arrayGrafico, 0, 7);
            }
        }
    }




    • Editado Andreclino sexta-feira, 22 de novembro de 2019 13:53
    sexta-feira, 22 de novembro de 2019 13:49