当前位置：首页 > ai >正文

Dijkstra‘s Algorithm Implementation

ai 2025/7/5 12:04:43

1、Dijkstra's Algorithm Implementation

（1）网页演示

（2）代码

<!DOCTYPE html>
<html lang="en">
<head><meta charset="UTF-8"><title>Shortest Path Visualization</title><style>body {font-family: Arial, sans-serif;max-width: 1200px;margin: 0 auto;padding: 20px;background-color: #f0f0f0;}.container {display: flex;gap: 30px;}.code-section {flex: 1;background: #282c34;padding: 20px;border-radius: 8px;color: #abb2bf;}.visualization {flex: 1;background: white;padding: 20px;border-radius: 8px;box-shadow: 0 2px 4px rgba(0,0,0,0.1);}pre {margin: 0;overflow-x: auto;}.keyword {color: #c678dd;}.function {color: #61afef;}.comment {color: #5c6370;font-style: italic;}.type {color: #e06c75;}.button {background: #4CAF50;color: white;padding: 10px 20px;border: none;border-radius: 4px;cursor: pointer;}.button:hover {background: #45a049;}</style>
</head>
<body><h1>Dijkstra's Algorithm Implementation</h1><div class="container"><div class="code-section"><h2 style="color: white;">C++ Implementation</h2><pre><code><span class="comment">// Dijkstra's algorithm using priority queue</span>
<span class="keyword">#include</span> <span class="type">&lt;vector&gt;</span>
<span class="keyword">#include</span> <span class="type">&lt;queue&gt;</span>
<span class="keyword">using</span> <span class="keyword">namespace</span> std;<span class="keyword">typedef</span> pair<span class="type">&lt;int, int&gt;</span> pii;<span class="type">vector</span><span class="type">&lt;int&gt;</span> <span class="function">dijkstra</span>(<span class="type">vector</span><span class="type">&lt;vector</span><span class="type">&lt;pii&gt;</span>&gt; &graph, int start) {int n = graph.size();<span class="type">vector</span><span class="type">&lt;int&gt;</span> dist(n, INT_MAX);priority_queue<span class="type">&lt;pii, vector</span><span class="type">&lt;pii&gt;</span>, greater<span class="type">&lt;pii&gt;</span>> pq;dist[start] = 0;pq.push({0, start});<span class="keyword">while</span> (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();<span class="keyword">if</span> (d > dist[u]) <span class="keyword">continue</span>;<span class="keyword">for</span> (auto &edge : graph[u]) {int v = edge.first;int w = edge.second;<span class="keyword">if</span> (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}<span class="keyword">return</span> dist;
}</code></pre></div><div class="visualization"><h2>Algorithm Visualization</h2><div id="graph-container"></div><button class="button" onclick="runDemo()">Run Demo</button><div id="output"></div></div></div><script>function runDemo() {const output = document.getElementById('output');output.innerHTML = `<h3>Sample Graph:</h3><p>Nodes: 5 (0-4)</p><p>Edges:<br>0 → 1 (4)<br>0 → 2 (1)<br>2 → 1 (2)<br>2 → 3 (5)<br>1 → 4 (4)<br>3 → 4 (1)</p><h3>Results from C++ implementation:</h3><p>Shortest distances from node 0:<br>Node 0: 0<br>Node 1: 3<br>Node 2: 1<br>Node 3: 6<br>Node 4: 7</p>`;}</script>
</body>
</html>

查看全文

http://www.xdnf.cn/news/2228.html