- No difference between shortest paths in directed and undirected graphs (undirected graph are special cases of directed graphs)
- Graph storage: dense graphs (adjacency matrix) && sparse graphs (adjacency list)
I. Single-Source Shortest Path
1. All edge weights are positive - Dijkstra's Algorithm
- Handling multiple edges and self-loops
- Self-loops never appear in shortest paths
- For multiple edges, keep only the shortest one
<html>
<head>
<title>Shortest Path Algorithm</title>
</head>
<body>
<script>
const INF = 0x3f3f3f3f;
let nodeCount, edgeCount;
let adjacencyMatrix = [];
let distances = [];
let visited = [];
function initializeGraph() {
adjacencyMatrix = Array(nodeCount + 1).fill().map(() => Array(nodeCount + 1).fill(INF));
distances = Array(nodeCount + 1).fill(INF);
visited = Array(nodeCount + 1).fill(false);
for (let i = 1; i <= nodeCount; i++) {
adjacencyMatrix[i][i] = 0;
}
}
function buildGraph() {
const input = prompt("Enter edges (format: start end weight):").split(' ');
for (let i = 0; i < edgeCount; i++) {
const start = parseInt(input[i * 3]);
const end = parseInt(input[i * 3 + 1]);
const weight = parseInt(input[i * 3 + 2]);
adjacencyMatrix[start][end] = Math.min(adjacencyMatrix[start][end], weight);
}
}
function dijkstra() {
distances[1] = 0;
for (let i = 0; i < nodeCount; i++) {
let current = -1;
for (let j = 1; j <= nodeCount; j++) {
if (!visited[j] && (current === -1 || distances[j] < distances[current])) {
current = j;
}
}
if (current === -1) break;
visited[current] = true;
for (let j = 1; j <= nodeCount; j++) {
if (adjacencyMatrix[current][j] !== INF) {
distances[j] = Math.min(distances[j], distances[current] + adjacencyMatrix[current][j]);
}
}
}
return distances[nodeCount] === INF ? -1 : distances[nodeCount];
}
function main() {
const input = prompt("Enter number of nodes and edges:").split(' ');
nodeCount = parseInt(input[0]);
edgeCount = parseInt(input[1]);
initializeGraph();
buildGraph();
const result = dijkstra();
alert("Shortest path distance: " + result);
}
main();
</script>
</body>
</html>
- Heap optimizaton for Dijkstra's algorithm
To be updated~~~
2. Edge weights may be negative
2.1 Bellman-Ford Algorithm
2.2 SPFA Algorithm
To be updated~~~SPFA Algorithm
II. All-Pairs Shortest Path - Floyd-Warhsall Algorithm
- Using adjacency matrix for graph storage
<html>
<head>
<title>All-Pairs Shortest Path</title>
</head>
<body>
<script>
const INF = 0x3f3f3f3f;
let nodeCount, edgeCount;
let distanceMatrix = [];
function initializeMatrix() {
distanceMatrix = Array(nodeCount + 1).fill().map(() => Array(nodeCount + 1).fill(INF));
for (let i = 1; i <= nodeCount; i++) {
distanceMatrix[i][i] = 0;
}
}
function buildGraph() {
const input = prompt("Enter edges (format: start end weight):").split(' ');
for (let i = 0; i < edgeCount; i++) {
const start = parseInt(input[i * 3]);
const end = parseInt(input[i * 3 + 1]);
const weight = parseInt(input[i * 3 + 2]);
distanceMatrix[start][end] = Math.min(distanceMatrix[start][end], weight);
}
}
function floydWarshall() {
for (let k = 1; k <= nodeCount; k++) {
for (let i = 1; i <= nodeCount; i++) {
for (let j = 1; j <= nodeCount; j++) {
if (distanceMatrix[i][k] !== INF && distanceMatrix[k][j] !== INF) {
distanceMatrix[i][j] = Math.min(distanceMatrix[i][j], distanceMatrix[i][k] + distanceMatrix[k][j]);
}
}
}
}
}
function main() {
const input = prompt("Enter number of nodes and edges:").split(' ');
nodeCount = parseInt(input[0]);
edgeCount = parseInt(input[1]);
initializeMatrix();
buildGraph();
floydWarshall();
console.log("All-pairs shortest path matrix:");
for (let i = 1; i <= nodeCount; i++) {
let row = [];
for (let j = 1; j <= nodeCount; j++) {
row.push(distanceMatrix[i][j] === INF ? "INF" : distanceMatrix[i][j]);
}
console.log(row.join(' '));
}
}
main();
</script>
</body>
</html>