کد ++C
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int MAX_INT = std::numeric_limits<int>::max();
typedef int Weight;
typedef int Node;
class Graph
{
public:
Graph(int vertexNumbers) :
adjList(vertexNumbers)
{}
void addEdge(int u, int v, int weight)
{
adjList[u].push_back(make_pair(weight, v));
}
vector < pair<Weight, Node>>& operator[](const Node& u)
{
return adjList[u];
}
vector<vector<pair<Weight, Node> > > adjList;
};
void dijkstra(Graph& g, const Node& s, vector<int>& d, vector<int>& p)
{
const int nodeNumbers = g.adjList.size();
d.resize(nodeNumbers);
p.resize(nodeNumbers);
for (int i = 0; i < nodeNumbers; i++){
p[i] = -1;
d[i] = MAX_INT;
}
d[s] = 0;
priority_queue<pair<Weight, Node> > Q;
Q.push(make_pair(0, s));
while (!Q.empty())
{
pair<int, int> elem = Q.top();
Node u = elem.second;
Q.pop();
vector<pair<Weight, Node> >& adj = g[elem.second];
for (vector<pair<Weight, Node> >::const_iterator it = adj.begin(); it != adj.end(); ++it)
{
Node v = it->second;
if (it->first + d[u] < d[v])
{
d[v] = it->first + d[u];
Q.push(make_pair(d[v], v));
p[v] = u;
}
}
}
}
void print_path(const vector<Node>& p, Node s, Node e)
{
std::cout << "Going from " << s + 1 << " To " << e + 1 << ": ";
while (e != -1 && p[e] != s)
{
cout << e + 1 << " ";
e = p[e];
}
if (e != -1)
cout << e + 1;
cout << " " << s + 1 << '\n';
}
int main()
{
Graph g(6);//graph pasokh bala
g.addEdge(0, 1, 7);
g.addEdge(0, 2, 9);
g.addEdge(0, 5, 14);
g.addEdge(1, 2, 10);
g.addEdge(1, 3, 15);
g.addEdge(1, 0, 7);
g.addEdge(2, 0, 0);
g.addEdge(2, 1, 10);
g.addEdge(2, 3, 11);
g.addEdge(2, 5, 2);
g.addEdge(3, 2, 11);
g.addEdge(3, 1, 15);
g.addEdge(3, 4, 6);
g.addEdge(4, 3, 6);
g.addEdge(4, 5, 9);
g.addEdge(5, 1, 14);
g.addEdge(5, 2, 2);
g.addEdge(5, 4, 9);
vector<int> d, p;
dijkstra(g, 0, d, p);
int idx = 0;
for (auto i : d)
std::cout << "cost of Going from " << 1 << " To " << ++idx << " is : " << i << '\n';
for (idx = 0; idx < 6; ++idx)
print_path(p, 0, idx);
}