所有边权非负
朴素(稠密图)
O(n²+m)
int g[N][N];//memset(g, 0x3f, sizeof g);
int dist[N];
bool st[N];
void dijkstra(int start)
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
for (int i = 0; i < n - 1; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || dist[t] > dist[j]))
{
t = j;
}
}
for (int j = 1; j <= n; j++)
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
st[t] = 1;
}
}
堆优化版(稀疏图)
O(mlogn)
int h[N], w[M], e[M], ne[M], idx; //memset(h, -1, sizeof h);
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void dijkstra(int start)
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
heap.push({0, start});
dist[start] = 0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int u = t.second, dis = t.first;
if (st[u])
{
continue;
}
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dis + w[i])
{
dist[j] = dis + w[i];
heap.push({dist[j], j});
}
}
}
}