5种语言实现 | 使用Dijkstra算法从起点到所有节点找到最短路径

Input: src = 0, the graph is shown below.

Output: 0 4 12 19 21 11 9 8 14
Explanation: The distance from 0 to 1 = 4.
The minimum distance from 0 to 2 = 12. 0->1->2
The minimum distance from 0 to 3 = 19. 0->1->2->3
The minimum distance from 0 to 4 = 21. 0->7->6->5->4
The minimum distance from 0 to 5 = 11. 0->7->6->5
The minimum distance from 0 to 6 = 9. 0->7->6
The minimum distance from 0 to 7 = 8. 0->7
The minimum distance from 0 to 8 = 14. 0->1->2->8

// C++ Program to find Dijkstra's shortest path using
// priority_queue in STL
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

// iPair ==> Integer Pair
typedef pair<int, int> iPair;

// This class represents a directed graph using
// adjacency list representation
class Graph {
  int V; // No. of vertices

  // In a weighted graph, we need to store vertex
  // and weight pair for every edge
  list<pair<int, int> >* adj;

public:
  Graph(int V); // Constructor

  // function to add an edge to graph
  void addEdge(int u, int v, int w);

  // prints shortest path from s
  void shortestPath(int s);
};

// Allocates memory for adjacency list
Graph::Graph(int V)
{
  this->V = V;
  adj = new list<iPair>[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));
}

// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
  // Create a priority queue to store vertices that
  // are being preprocessed. This is weird syntax in C++.
  // Refer below link for details of this syntax
  // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
  priority_queue<iPair, vector<iPair>, greater<iPair> >
    pq;

  // Create a vector for distances and initialize all
  // distances as infinite (INF)
  vector<int> dist(V, INF);

  // Insert source itself in priority queue and initialize
  // its distance as 0.
  pq.push(make_pair(0, src));
  dist[src] = 0;

  /* Looping till priority queue becomes empty (or all
  distances are not finalized) */
  while (!pq.empty()) {
    // 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)
    int u = pq.top().second;
    pq.pop();

    // 'i' is used to get all adjacent vertices of a
    // vertex
    list<pair<int, int> >::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i) {
      // Get vertex label and weight of current
      // adjacent of u.
      int v = (*i).first;
      int weight = (*i).second;

      // If there is shorted path to v through u.
      if (dist[v] > dist[u] + weight) {
        // Updating distance of v
        dist[v] = dist[u] + weight;
        pq.push(make_pair(dist[v], v));
      }
    }
  }

  // Print shortest distances stored in dist[]
  printf("Vertex Distance from Source\n");
  for (int i = 0; i < V; ++i)
    printf("%d \t\t %d\n", i, dist[i]);
}

// Driver's code
int main()
{
  // create the graph given in above figure
  int V = 9;
  Graph g(V);

  // making above shown graph
  g.addEdge(0, 1, 4);
  g.addEdge(0, 7, 8);
  g.addEdge(1, 2, 8);
  g.addEdge(1, 7, 11);
  g.addEdge(2, 3, 7);
  g.addEdge(2, 8, 2);
  g.addEdge(2, 5, 4);
  g.addEdge(3, 4, 9);
  g.addEdge(3, 5, 14);
  g.addEdge(4, 5, 10);
  g.addEdge(5, 6, 2);
  g.addEdge(6, 7, 1);
  g.addEdge(6, 8, 6);
  g.addEdge(7, 8, 7);

  // Function call
  g.shortestPath(0);

  return 0;
}

import java.util.*;

class Graph {
  private int V;
  private List<List<iPair>> adj;

  Graph(int V) {
    this.V = V;
    adj = new ArrayList<>();
    for (int i = 0; i < V; i++) {
      adj.add(new ArrayList<>());
    }
  }

  void addEdge(int u, int v, int w) {
    adj.get(u).add(new iPair(v, w));
    adj.get(v).add(new iPair(u, w));
  }

  void shortestPath(int src) {
    PriorityQueue<iPair> pq = new PriorityQueue<>(V, Comparator.comparingInt(o -> o.first));
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);

    pq.add(new iPair(0, src));
    dist[src] = 0;

    while (!pq.isEmpty()) {
      int u = pq.poll().second;

      for (iPair v : adj.get(u)) {
        if (dist[v.first] > dist[u] + v.second) {
          dist[v.first] = dist[u] + v.second;
          pq.add(new iPair(dist[v.first], v.first));
        }
      }
    }

    System.out.println("Vertex Distance from Source");
    for (int i = 0; i < V; i++) {
      System.out.println(i + "\t\t" + dist[i]);
    }
  }

  static class iPair {
    int first, second;

    iPair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }
}

public class Main {
  public static void main(String[] args) {
    int V = 9;
    Graph g = new Graph(V);

    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);

    g.shortestPath(0);
  }
}

import heapq

# iPair ==> Integer Pair
iPair = tuple

# This class represents a directed graph using
# adjacency list representation
class Graph:
  def __init__(self, V: int): # Constructor
    self.V = V
    self.adj = [[] for _ in range(V)]

  def addEdge(self, u: int, v: int, w: int):
    self.adj[u].append((v, w))
    self.adj[v].append((u, w))

  # Prints shortest paths from src to all other vertices
  def shortestPath(self, src: int):
    # Create a priority queue to store vertices that
    # are being preprocessed
    pq = []
    heapq.heappush(pq, (0, src))

    # Create a vector for distances and initialize all
    # distances as infinite (INF)
    dist = [float('inf')] * self.V
    dist[src] = 0

    while pq:
      # The first vertex in pair is the minimum distance
      # vertex, extract it from priority queue.
      # vertex label is stored in second of pair
      d, u = heapq.heappop(pq)

      # 'i' is used to get all adjacent vertices of a
      # vertex
      for v, weight in self.adj[u]:
        # If there is shorted path to v through u.
        if dist[v] > dist[u] + weight:
          # Updating distance of v
          dist[v] = dist[u] + weight
          heapq.heappush(pq, (dist[v], v))

    # Print shortest distances stored in dist[]
    for i in range(self.V):
      print(f"{i} \t\t {dist[i]}")

# Driver's code
if __name__ == "__main__":
  # create the graph given in above figure
  V = 9
  g = Graph(V)

  # making above shown graph
  g.addEdge(0, 1, 4)
  g.addEdge(0, 7, 8)
  g.addEdge(1, 2, 8)
  g.addEdge(1, 7, 11)
  g.addEdge(2, 3, 7)
  g.addEdge(2, 8, 2)
  g.addEdge(2, 5, 4)
  g.addEdge(3, 4, 9)
  g.addEdge(3, 5, 14)
  g.addEdge(4, 5, 10)
  g.addEdge(5, 6, 2)
  g.addEdge(6, 7, 1)
  g.addEdge(6, 8, 6)
  g.addEdge(7, 8, 7)

  g.shortestPath(0)

using System;
using System.Collections.Generic;

// This class represents a directed graph using
// adjacency list representation
public class Graph
{
private const int INF = 2147483647;

private int V;
private List<int[]>[] adj;

public Graph(int V)
{ 
  // No. of vertices
  this.V = V;
  // In a weighted graph, we need to store vertex
  // and weight pair for every edge
  this.adj = new List<int[]>[V];

  for (int i = 0; i < V; i++)
  {
  this.adj[i] = new List<int[]>();
  }
}

public void AddEdge(int u, int v, int w)
{
  this.adj[u].Add(new int[] { v, w });
  this.adj[v].Add(new int[] { u, w });
}

// Prints shortest paths from src to all other vertices
public void ShortestPath(int src)
{
  // Create a priority queue to store vertices that
  // are being preprocessed.
  SortedSet<int[]> pq = new SortedSet<int[]>(new DistanceComparer());

  // Create an array for distances and initialize all
  // distances as infinite (INF)
  int[] dist = new int[V];
  for (int i = 0; i < V; i++)
  {
  dist[i] = INF;
  }

  // Insert source itself in priority queue and initialize
  // its distance as 0.
  pq.Add(new int[] { 0, src });
  dist[src] = 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 by distance)
  int[] minDistVertex = pq.Min;
  pq.Remove(minDistVertex);
  int u = minDistVertex[1];

  // 'i' is used to get all adjacent vertices of a
  // vertex
  foreach (int[] adjVertex in this.adj[u])
  {
    // Get vertex label and weight of current
    // adjacent of u.
    int v = adjVertex[0];
    int weight = adjVertex[1];

    // If there is a shorter path to v through u.
    if (dist[v] > dist[u] + weight)
    {
    // Updating distance of v
    dist[v] = dist[u] + weight;
    pq.Add(new int[] { dist[v], v });
    }
  }
  }

  // Print shortest distances stored in dist[]
  Console.WriteLine("Vertex Distance from Source");
  for (int i = 0; i < V; ++i)
  Console.WriteLine(i + "\t" + dist[i]);
}

private class DistanceComparer : IComparer<int[]>
{
  public int Compare(int[] x, int[] y)
{
  if (x[0] == y[0])
  {
    return x[1] - y[1];
  }
  return x[0] - y[0];
  }
}
}

public class Program
{ 
// Driver Code
public static void Main()
{
  // create the graph given in above figure
  int V = 9;
  Graph g = new Graph(V);

  // making above shown graph
  g.AddEdge(0, 1, 4);
  g.AddEdge(0, 7, 8);
  g.AddEdge(1, 2, 8);
  g.AddEdge(1, 7, 11);
  g.AddEdge(2, 3, 7);
  g.AddEdge(2, 8, 2);
  g.AddEdge(2, 5, 4);
  g.AddEdge(3, 4, 9);
  g.AddEdge(3, 5, 14);
  g.AddEdge(4, 5, 10);
  g.AddEdge(5, 6, 2);
  g.AddEdge(6, 7, 1);
  g.AddEdge(6, 8, 6);
  g.AddEdge(7, 8, 7);
  g.ShortestPath(0);
}
}

// this code is contributed by bhardwajji

<script> 
// javascript Program to find Dijkstra's shortest path using
// priority_queue in STL
const INF = 2147483647;

// This class represents a directed graph using
// adjacency list representation
class Graph {

  constructor(V){

    // No. of vertices
    this.V = V;

    // In a weighted graph, we need to store vertex
    // and weight pair for every edge
    this.adj = new Array(V);
    for(let i = 0; i < V; i++){
      this.adj[i] = new Array();
    }
  }

  addEdge(u, v, w)
  {
    this.adj[u].push([v, w]);
    this.adj[v].push([u, w]);
  }

  // Prints shortest paths from src to all other vertices
  shortestPath(src)
  {
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
    let pq = [];

    // Create a vector for distances and initialize all
    // distances as infinite (INF)
    let dist = new Array(V).fill(INF);

    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.push([0, src]);
    dist[src] = 0;

    /* Looping till priority queue becomes empty (or all
    distances are not finalized) */
    while (pq.length > 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)
      let u = pq[0][1];
      pq.shift();

      // 'i' is used to get all adjacent vertices of a
      // vertex
      for(let i = 0; i < this.adj[u].length; i++){

        // Get vertex label and weight of current
        // adjacent of u.
        let v = this.adj[u][i][0];
        let weight = this.adj[u][i][1];

        // If there is shorted path to v through u.
        if (dist[v] > dist[u] + weight) {
          // Updating distance of v
          dist[v] = dist[u] + weight;
          pq.push([dist[v], v]);
          pq.sort((a, b) =>{
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
          });
        }
      }
    }

    // Print shortest distances stored in dist[]
    document.write("Vertex Distance from Source");
    for (let i = 0; i < V; ++i)
      document.write(i, "   ", dist[i]);
  }
}

// Driver's code
// create the graph given in above figure
let V = 9;
let g = new Graph(V);

// making above shown graph
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);

// Function call
g.shortestPath(0);

// The code is contributed by Nidhi goel. 
</script>