# 다익스트라

12개의 포스트

[알고리즘] 다익스트라

다익스트라 알고리즘 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제 1) 다익스트라 알고리즘 로직 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사 첫 정

2020년 6월 22일
·
0개의 댓글

[프로그래머스] 배달 (JavaScript)

프로그래머스 배달자바스크립트로 다익스트라를 구현해보았다.2차원 배열 만들기 (인접리스트로 사용)Array.from(Array(length), () => new Array());우선순위 큐 만들기거리로 오름차순 정렬되도록 만들었다.즉시실행함수를 사용했다.

2020년 5월 5일
·
0개의 댓글

[프로그래머스] 배달 (Java)

프로그래머스 배달다익스트라 알고리즘을 이용해서 최단거리를 구하는 문제였다. 다익스트라는 현재 저장된 거리와 새로 도달가능한 거리를 비교해 최단거리를 갱신해나가는 알고리즘이다.우선순위 큐를 이용해서 효율을 높인다.인접리스트 사용

2020년 5월 5일
·
0개의 댓글

Algorithm(Dijkstra)

다익스트라 알고리즘

2020년 4월 29일
·
0개의 댓글

[BOJ 1504] 특정한 최단경로 (Java)

BOJ 1504 특정한 최단경로이 문제는 최단경로를 구하는 문제지만 다음과 같은 특징을 가지고 있다.방문했던 정점, 간선을 재방문 할 수 있다. 방문체크를 하지않는다.특정한 두 정점을 반드시 지나서 도착해야한다. 시작점 - A - B - 도착점 , 시작점 - B -

2020년 2월 27일
·
0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제 3 철인 N종 경기

image.png 문제 파악 > 두 선수의 기록 시간이 동일하면서 최소 시간으로 운동 종목을 선택하는 문제이다. 종목을 선택하는 것을 간선으로 보는 것을 제외하고선, 그래프로 보는 사고가 생각나지 않아 해결하지 못했다. 문제 풀이 > 문제 풀이의 핵심은 이 전에 풀었던 문제인 어린이날 문제와 유사하다. 어린이날 문제는 간선을 선택으로 정점을 나머지로 ...

2019년 7월 23일
·
0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제2 - 소방차

image.png 문제 파악 > 최단 거리를 구하는 문제지만 특이한 조건들로 인해 간단히 접근할 수 없다. 먼저 정점들이 소방서, 불난 곳, 불나지 않은 곳으로 나뉘어져 있다. 불난 곳들과 소방서 사이의 최단 거리를 구해야 한다. 따라서 정점마다 가장 가까운 소방서가 다르고 이에 따라 다익스트라 알고리즘을 여러번 돌리는 과정이 필요하게 되어 시간 제한을...

2019년 7월 22일
·
0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제1 ROUTING

image.png 문제 풀이 > 다익스트라 알고리즘의 새로운 간선의 가중치를 더하는 부분을 곱하기로 바꿔주면 된다. 이 때 우선순위 큐의 초기값으로 0이 아닌 1 또는 -1을 넣어줘야 하는 것을 주의 해야 한다. 초기값이 0이 아니라 노이즈가 없는 경우 1이기 때문이다. 느낀점 > 복잡한 소수점 계산의 경우 long double 형을 사용할 수 있다....

2019년 7월 22일
·
0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘

다익스트라 알고리즘이란 > 다익스트라 알고리즘은 그래프의 정점들 사이에 가중치가 주어졌을 때 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다. > 다익스트라를 비롯한 대부분의 최단 거리 알고리즘은 음수 가중치를 갖는 간선이 있는 경우 음수 싸이클을 돌면서 가중치의 총합을 발산하는 경로가 생길 수 있어서 최단 거리를 계산할 수 없다. 다익스...

2019년 7월 22일
·
0개의 댓글
post-thumbnail

백준 1719 택배

문제 n개의 정점, m개의 간선이 주어집니다. 간선의 정보는 1) 시작 점, 2) 도착 점, 3) 가중치 입니다. 간선의 양방향입니다. 사진과 같이 시작 정점에서 다른 정점으로 최단 경로로 가기 위해 첫번째로 경유하는 정점들을 경로표로 출력하세요. n(1 <= n <= 200) 정점의 수, m(1 <= m <= 10000) 간선의 수 시간 제한 2초 문제...

2019년 2월 24일
·
0개의 댓글

programmers 배달

링크 세줄 요약 한 정점에서 모든 정점으로의 최단거리를 구해야한다. 모든 간선의 가중치가 양수이다. 위 두 조건을 만족하는 최단 경로를 알고리즘은 다익스트라 알고리즘이다.

2019년 1월 27일
·
0개의 댓글
post-thumbnail

[알고리즘] Dijkstra in python3

파이썬의 heapq 모듈을 이용해서 직접 priority queue를 구현해서 사용했고, 그래프를 그리기 위해 networkx 모듈을 사용했습니다. (코드를 돌려보시려면 설치하셔야 됩니다!) 강의는 링크에서 들으실수 있습니다.

2018년 11월 15일
·
2개의 댓글