Grafos de Dijkstra: Avaliação de Curtos-Circuitos
Resumo
Neste trabalho, revisitamos os grafos de Dijkstra e o conceito de programação estruturada. Apresentamos uma generalização desses grafos, admitindo avaliações de curtos-circuitos por meio de uma nova classe de grafos: os grafos de curto-circuito. Introduzimos um algoritmo que contrai esses curtoscircuitos e reduz essa nova classe aos grafos de Dijkstra.
Palavras-chave:
Algoritmos em grafos, Programação estruturada, Avaliação de curto-circuito, Grafos de Dijkstra
Referências
Allen, F. E. (1970). Control flow analysis. SIGPLAN Not., 5(7):1–19. DOI: 10.1145/390013.80847
Bento, L. M., Boccardo, D. R., Machado, R. C., Miyazawa, F. K., Pereira de Sá, V. G., and Szwarcfiter, J. L. (2019). Dijkstra graphs. Discrete Applied Mathematics, 261:52–62. GO X Meeting, Rigi Kaltbad (CH), July 10–14, 2016. DOI: 10.1016/j.dam.2017.07.033
Dahl, O.-J., Dijkstra, E. W., and Hoare, C. A. R. (1972). Structured Programming. Academic Press London and New York.
Dijkstra, E. W. (1968). Letters to the editor: go to statement considered harmful. Commun. ACM, 11(3):147–148. DOI: 10.1145/362929.362947
Bento, L. M., Boccardo, D. R., Machado, R. C., Miyazawa, F. K., Pereira de Sá, V. G., and Szwarcfiter, J. L. (2019). Dijkstra graphs. Discrete Applied Mathematics, 261:52–62. GO X Meeting, Rigi Kaltbad (CH), July 10–14, 2016. DOI: 10.1016/j.dam.2017.07.033
Dahl, O.-J., Dijkstra, E. W., and Hoare, C. A. R. (1972). Structured Programming. Academic Press London and New York.
Dijkstra, E. W. (1968). Letters to the editor: go to statement considered harmful. Commun. ACM, 11(3):147–148. DOI: 10.1145/362929.362947
Publicado
10/09/2025
Como Citar
GUEDES, André L. P.; FEITOSA, Matheus S.; BATISTA, Matheus T..
Grafos de Dijkstra: Avaliação de Curtos-Circuitos. In: WORKSHOP-ESCOLA DE INFORMÁTICA TEÓRICA (WEIT), 8. , 2025, Ponta Grossa/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 202-207.
