>
나는 Dijkstra의 알고리즘을 더 잘 이해하려고 노력하고있다. 교과서에있는 알고리즘 이미지를 첨부했습니다. 의사 코드는 입력이 방향이없는 그래프임을 나타내지 만, 방향이 지정된 그래프에 대해 알고리즘이 다른가? 유 방향 그래프의 입력으로 알고리즘을 살펴 보았으며 차이점을 식별하지 못했습니다.

Algorithm ShortestPath(G, v)
Input: A simple undirected weighted graph G with nonnegative edge weights and a distinguished vertex v of G
Output: A label D[u], for each vertex u of G, such that D[u] is the length of a shortest path from v to u in G
Initialize D[v]<--0 and D[u]<--+infinity for each vertex u != v.
Let priority queue Q contain all the vertices of G using the D labels as keys.
while Q is not empty do
    {pull a new vertex u into the cloud}
u<-- Q.removeMin()
for each vertex z adjacent to u such that z is in Q do
    {preform the relaxation procedure on edge (u,z)}
    if D[u]+w((u,z))<D[z] then
         D[z]<-- D[u]+w((u,z))
         change to D[z] the of vertex z in Q
return the label D[u] of each vertex u

  • 답변 # 1

    인접 목록에서 이동할 가장자리가있을 때 PriorityQueue에 가장자리를 추가하기 때문에 직접 및 비 방향 그래프 모두에서 Dijkstra의 알고리즘을 사용할 수 있습니다. 예를 들어, 노드 중 하나에 가중치 3의 A에서 B까지의 모서리가있는 경우 BI에서 지시 된 경우 AI에서 모서리를 다시 A에 추가 할 수 없지만 AI에서 B에 추가 할 수 있습니다.

    다른 답변과 마찬가지로 가중치와 혼동하지 마십시오. Dijkstra의 알고리즘은 양의 계량 그래프에서 실행됩니다. 그렇지 않으면 우선 순위 대기열이 쓸모가 없습니다.

  • 이전 javascript - 페이지 리디렉션이 사용될 때 Firebase가 업데이트되지 않습니다
  • 다음 python - 여러 범주 형 변수를 고르게 표현하여 데이터 프레임에서 목록 생성