GRAFOS – RIO GRANDE DO SUL
Por: Juliana2017 • 7/7/2018 • 657 Palavras (3 Páginas) • 453 Visualizações
...
{
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 ListResultado>();
for (int i = 0; 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;
ListString> S = new Liststring>(); //Solução
ListString> Q = new Liststring>(); //Todos os Vertices pertencentes ao grafo
String u = "";//carregado sempre com o vertice que tenha o menor d, a cada volta do while
int iDestino = 1;
int iOrigem = 1;
for (int i = 0; i
{
Q.Add(Origens[i].ToString());//Atribui todos os vertices
iOrigem = indOrigem(origem, Adj);
if (Origens[i].ToString() == origem)//verifica se é origem
{//sim
d[iOrigem, 0] = origem;//d[i,1] = Nome da Origem
d[iOrigem, 1] = "0";//d[i,2] = Distancia da origem
pi[iOrigem, 0] = origem;//pi[i,1] = Nome da Origem
pi[iOrigem, 1] = "NILL";//pi[i,2] = Pai da origem
}
else
{//não
d[i, 0] = Origens[i].ToString();//d[i,1] = Nome
d[i, 1] = "999999999";//d[i,2] = Distancia
pi[i, 0] = Origens[i].ToString();//pi[i,1] = Nome
pi[i, 1] = "-";//pi[i,2] = Pai
}
}
while (Q.Count != 0){//enquanto existir vertice não ligado
u = menorQ(d, Q); // Menor valor de d em Q
iOrigem = indOrigem(u, Adj);
S.Add(u);//compondo conjunto Solução do grafo
Q.Remove(u);//retirar do Q
iDestino = indDestino(iOrigem, Adj, d);
for (int y = 1; y = 0;y++){
if (AdjDist[iOrigem, y] != "-" && (Convert.ToInt32(d[iOrigem, 1]) + Convert.ToInt32(AdjDist[iOrigem, y]) Convert.ToInt32(d[iDestino, 1])))
{
d[iDestino, 1] = (Convert.ToInt32(d[iOrigem, 1]) + Convert.ToInt32(AdjDist[iOrigem, y])).ToString();
pi[iDestino, 1] = u;
}
iDestino = indDestino(iOrigem, Adj, d);
}
}
}
private int indOrigem(String u, String[,] Adj)
{
for (int i = 0; i
{
if (Adj[i, 0] == u)
{
return i;
}
}
return -1;//Não foi encontrado a Origem
}
private int indDestino(Int32 iOrigem, String[,] Adj, String[,] d)
{
for (int i = 1; i
{
if (Adj[iOrigem, i] != null)
{
int k = 0;
while (Adj[iOrigem, i] != d[k,0])
{
k++;
}
Adj[iOrigem, i] = null;
return k;
}
}
return -1;//Não foi encontrado a Destino
}
private String menorQ(String[,] d, ListString> Q)
{
int
...