// Program to find Dijkstra's shortest path using // priority_queue in STL #include  using namespace std; #define INF 0x3f3f3f3f // iPair ==>정수 쌍 typedef 쌍 아이페어; // 이 클래스는 // 인접 목록 표현을 사용하여 유향 그래프를 나타냅니다. class Graph { int V; // 정점 수 // 가중치 그래프에서는 // 모든 간선 목록에 대해 정점과 가중치 쌍을 저장해야 합니다.>* 조정; 공개: 그래프(int V); // 생성자 // 그래프에 간선을 추가하는 함수 void addEdge(int u, int v, int w);  // s에서 최단 경로를 인쇄합니다. void shortestPath(int s); }; // 인접 목록에 대한 메모리 할당 Graph::Graph(int V) { this->V = V;  adj = 새 목록 [V]; } void Graph::addEdge(int u, int v, int w) { adj[u].push_back(make_pair(v, w));  adj[v].push_back(make_pair(u, w)); } // src에서 다른 모든 정점까지의 최단 경로를 인쇄합니다. void Graph::shortestPath(int src) { // 전처리 중인 정점을 저장하기 위해 // 우선순위 대기열을 생성합니다. 이것은 C++의 이상한 구문입니다.  // 이 구문에 대한 자세한 내용은 아래 링크를 참조하세요. // https://www.techcodeview.com Priority_queue , 보다 큰 > pq;  // 거리에 대한 벡터를 생성하고 // 모든 거리를 무한(INF) 벡터로 초기화합니다. dist(V,INF);  // 소스 자체를 우선순위 큐에 삽입하고 // 거리를 0으로 초기화합니다. pq.push(make_pair(0, src));  거리[src] = 0;  /* 우선순위 큐가 비워질 때까지(또는 모든 거리가 확정되지 않을 때까지 반복) */ while (!pq.empty()) { // 쌍의 첫 번째 정점은 최소 거리입니다. // 정점, 우선순위 큐에서 추출합니다.  // 정점 레이블은 쌍의 두 번째 항목에 저장됩니다(정점을 유지하려면 // 이 방법을 사용해야 합니다. // 정렬된 거리(거리는 // 쌍의 첫 번째 항목이어야 합니다) int u = pq.top().second; pq.pop(); // 'i'는 정점 목록의 모든 인접 정점을 가져오는 데 사용됩니다.>::반복자 i;  for (i = adj[u].begin(); i != adj[u].end(); ++i) { // 정점 레이블과 현재 // u에 인접한 가중치를 가져옵니다.  int v = (*i).first;  int 가중치 = (*i).second;  // u를 통해 v로의 단축 경로가 있는 경우.  if (dist[v]> dist[u] + Weight) { // v의 거리 업데이트 dist[v] = dist[u] + Weight;  pq.push(make_pair(dist[v], v));  } } } // dist[]에 저장된 최단 거리를 인쇄합니다. printf('소스로부터의 정점 거리
');  for (int i = 0; i< V; ++i)  printf('%d 		 %d
', i, dist[i]); } // Driver program to test methods of graph class int main() {  // create the graph given in above figure  int V = 7;  Graph g(V);  // making above shown graph  g.addEdge(0, 1, 2);  g.addEdge(0, 2, 6);  g.addEdge(1, 3, 5);  g.addEdge(2, 3, 8);  g.addEdge(3, 4, 10);  g.addEdge(3, 5, 15);  g.addEdge(4, 6, 2);  g.addEdge(5, 6, 6);  g.shortestPath(0);  return 0; }>

import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.PriorityQueue; public class DijkstraAlgoForShortestDistance {  static class Node implements Comparable{ int v;  정수 거리;  공개 노드(int v, int distance) { this.v = v;  this.distance = 거리;  } @Override public int CompareTo(Node n) { if (this.distance<= n.distance) {  return -1;  }  else {  return 1;  }  }  }  static int[] dijkstra(  int V,  ArrayList >> adj, int S) { boolean[] 방문 = new boolean[V];  해시맵 map = 새로운 HashMap();  우선순위 대기열q = 새로운 우선순위큐();  map.put(S, new Node(S, 0));  q.add(새 노드(S, 0));  while (!q.isEmpty()) { 노드 n = q.poll();  int v = n.v;  int 거리 = n.거리;  방문[v] = true;  배열목록 > adjList = adj.get(v);  for(ArrayList adjLink : adjList) { if (visited[adjLink.get(0)] == false) { if (!map.containsKey(adjLink.get(0))) { map.put( adjLink.get(0), new Node (v, 거리 + adjLink.get(1)));  } else { 노드 sn = map.get(adjLink.get(0));  if (거리 + adjLink.get(1)< sn.distance) {  sn.v = v;  sn.distance  = distance + adjLink.get(1);  }  }  q.add(new Node(adjLink.get(0),  distance  + adjLink.get(1)));  }  }  }  int[] result = new int[V];  for (int i = 0; i < V; i++) {  result[i] = map.get(i).distance;  }  return result;  }  public static void main(String[] args)  {  ArrayList >> 조정 = 새로운 ArrayList();  해시맵 >> 지도 = 새로운 HashMap();  정수 V = 6;  정수 E = 5;  int[] u = { 0, 0, 1, 2, 4 };  int[] v = { 3, 5, 4, 5, 5 };  int[] w = { 9, 4, 4, 10, 3 };  for (int i = 0; i< E; i++) {  ArrayList 가장자리 = 새로운 ArrayList();  edge.add(v[i]);  edge.add(w[i]);  배열목록 > 조정목록;  if (!map.containsKey(u[i])) { adjList = new ArrayList();  } else { adjList = map.get(u[i]);  } adjList.add(가장자리);  map.put(u[i], adjList);  배열목록 edge2 = 새로운 ArrayList();  edge2.add(u[i]);  edge2.add(w[i]);  배열목록 > 조정목록2;  if (!map.containsKey(v[i])) { adjList2 = new ArrayList();  } else { adjList2 = map.get(v[i]);  } adjList2.add(edge2);  map.put(v[i], adjList2);  } for (int i = 0; i< V; i++) {  if (map.containsKey(i)) {  adj.add(map.get(i));  }  else {  adj.add(null);  }  }  int S = 1;  // Input sample  //[0 [[3, 9], [5, 4]],  // 1 [[4, 4]],  // 2 [[5, 10]],  // 3 [[0, 9]],  // 4 [[1, 4], [5, 3]],  // 5 [[0, 4], [2, 10], [4, 3]]  //]  int[] result  = DijkstraAlgoForShortestDistance.dijkstra(  V, adj, S);  System.out.println(Arrays.toString(result));  } }>

# Python implementation of Dijkstra Algorithm import heapq class Node: def __init__(self, v, distance): self.v = v self.distance = distance def __lt__(self, other): return self.distance < other.distance def dijkstra(V, adj, S): visited = [False] * V map = {} q = [] map[S] = Node(S, 0) heapq.heappush(q, Node(S, 0)) while q: n = heapq.heappop(q) v = n.v distance = n.distance visited[v] = True adjList = adj[v] for adjLink in adjList: if not visited[adjLink[0]]: if adjLink[0] not in map: map[adjLink[0]] = Node(v, distance + adjLink[1]) else: sn = map[adjLink[0]] if distance + adjLink[1] < sn.distance: sn.v = v sn.distance = distance + adjLink[1] heapq.heappush(q, Node(adjLink[0], distance + adjLink[1])) result = [0] * V for i in range(V): result[i] = map[i].distance return result def main(): adj = [[] for _ in range(6)] V = 6 E = 5 u = [0, 0, 1, 2, 4] v = [3, 5, 4, 5, 5] w = [9, 4, 4, 10, 3] for i in range(E): edge = [v[i], w[i]] adj[u[i]].append(edge) edge2 = [u[i], w[i]] adj[v[i]].append(edge2) S = 1 result = dijkstra(V, adj, S) print(result) if __name__ == '__main__': main() # This code is contributed by ragul21>

// C# Code: using System; using System.Collections.Generic; public class Graph {  // No. of vertices  private int V;  // adjacency list  private List>[] 조정;  // 생성자 public Graph(int v) { V = v;  adj = 새 목록>[ v ];  for (int i = 0; i< v; ++i)  adj[i] = new List>();  } // 그래프에 간선을 추가하는 함수 public void addEdge(int u, int v, int w) { adj[u].Add(Tuple.Create(v, w));  adj[v].Add(Tuple.Create(u, w));  } // s에서 최단 경로를 인쇄합니다. public void shortestPath(int s) { // 전처리 중인 정점을 저장하기 위해 // 우선순위 대기열을 만듭니다.  var pq = 새로운 PriorityQueue>();  // 거리에 대한 벡터를 생성하고 // 모든 거리를 무한(INF)으로 초기화합니다. var dist = new int[V];  for (int i = 0; i< V; i++)  dist[i] = int.MaxValue;  // Insert source itself in priority queue and  // initialize its distance as 0.  pq.Enqueue(Tuple.Create(0, s));  dist[s] = 0;  /* Looping till priority queue becomes empty (or all  distances are not finalized) */  while (pq.Count != 0) {  // The first vertex in pair is the minimum  // distance vertex, extract it from priority  // queue. vertex label is stored in second of  // pair (it has to be done this way to keep the  // vertices sorted distance (distance must be  // first item in pair)  var u = pq.Dequeue().Item2;  // 'i' is used to get all adjacent vertices of a  // vertex  foreach(var i in adj[u])  {  // Get vertex label and weight of current  // adjacent of u.  int v = i.Item1;  int weight = i.Item2;  // If there is shorted path to v through u.  if (dist[v]>dist[u] + Weight) { // v의 거리 업데이트 dist[v] = dist[u] + Weight;  pq.Enqueue(Tuple.Create(dist[v], v));  } } } // dist[]에 저장된 최단 거리를 인쇄합니다. Console.WriteLine('소스로부터의 정점 거리');  for (int i = 0; i< V; ++i)  Console.WriteLine('{0}		{1}', i, dist[i]);  } } public class PriorityQueue{ 개인 읽기 전용 목록_데이터;  개인 읽기 전용 비교_비교;  공개 PriorityQueue(): this(비교.기본값) { } 공개 PriorityQueue(IComparer비교): this(비교.비교) { } 공개 PriorityQueue(비교비교) { _data = 새 목록();  _비교 = 비교;  } public void Enqueue(T 항목) { _data.Add(item);  var childIndex = _data.Count - 1;  while (childIndex> 0) { var parentIndex = (childIndex - 1) / 2;  if (_compare(_data[childIndex], _data[parentIndex])>= 0) break;  T tmp = _data[childIndex];  _data[childIndex] = _data[parentIndex];  _data[parentIndex] = tmp;  childIndex = 부모인덱스;  } } public T Dequeue() { // pq가 비어 있지 않다고 가정합니다. 호출 코드까지 var lastElement = _data.Count - 1;  var 앞항목 = _data[0];  _data[0] = _data[마지막요소];  _data.RemoveAt(lastElement);  --lastElement;  var parentIndex = 0;  while (true) { var childIndex = parentIndex * 2 + 1;  if (childIndex> lastElement) 브레이크; // 트리 끝 var rightChild = childIndex + 1;  if(오른쪽자식<= lastElement  && _compare(_data[rightChild],  _data[childIndex])  < 0)  childIndex = rightChild;  if (_compare(_data[parentIndex],  _data[childIndex])  <= 0)  break; // Correct position  T tmp = _data[parentIndex];  _data[parentIndex] = _data[childIndex];  _data[childIndex] = tmp;  parentIndex = childIndex;  }  return frontItem;  }  public T Peek()  {  T frontItem = _data[0];  return frontItem;  }  public int Count  {  get { return _data.Count; }  } } class Program {  // Driver program to test methods of graph class  static void Main(string[] args)  {  // create the graph given in above figure  int V = 7;  Graph g = new Graph(V);  // making above shown graph  g.addEdge(0, 1, 2);  g.addEdge(0, 2, 6);  g.addEdge(1, 3, 5);  g.addEdge(2, 3, 8);  g.addEdge(3, 4, 10);  g.addEdge(3, 5, 15);  g.addEdge(4, 6, 2);  g.addEdge(5, 6, 6);  g.shortestPath(0);  } }>

class PriorityQueue {  constructor() {  this.queue = [];  }  enqueue(element, priority) {  this.queue.push({ element, priority });  this.queue.sort((a, b) =>a.우선순위 - b.우선순위);  } dequeue() { if (this.isEmpty()) { return null;  } return this.queue.shift().element;  } isEmpty() { return this.queue.length === 0;  } } 클래스 그래프 { 생성자(V) { this.V = V;  this.adj = 새로운 배열(V);  for (나는 = 0이라고 하자; 나는< V; i++) {  this.adj[i] = [];  }  }  addEdge(u, v, w) {  this.adj[u].push({ v, w });  this.adj[v].push({ v: u, w });  }  shortestPath(src) {  const pq = new PriorityQueue();  const dist = new Array(this.V).fill(Infinity);  const visited = new Array(this.V).fill(false);  pq.enqueue(src, 0);  dist[src] = 0;  while (!pq.isEmpty()) {  const u = pq.dequeue();  if (visited[u]) continue;  visited[u] = true;  for (const { v, w } of this.adj[u]) {  if (!visited[v] && dist[u] + w < dist[v]) {  dist[v] = dist[u] + w;  pq.enqueue(v, dist[v]);  }  }  }  console.log('Vertex Distance from Source');  for (let i = 0; i < this.V; i++) {  console.log(`${i}		${dist[i] === Infinity ? 'Infinity' : dist[i]}`);  }  } } function main() {  const V = 7;  const g = new Graph(V);  g.addEdge(0, 1, 2);  g.addEdge(0, 2, 6);  g.addEdge(1, 3, 5);  g.addEdge(2, 3, 8);  g.addEdge(3, 4, 10);  g.addEdge(3, 5, 15);  g.addEdge(4, 6, 2);  g.addEdge(5, 6, 6);  g.shortestPath(0); } main();>