Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
dijkstra's algo
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//g++ 7.4.0 #include <iostream> #include <vector> using namespace std; vector<int> graph[10]; bool used[10]; int leng[10][10]; // находим неиспользованную вершину с наименьшим до нее расстоянием int nextVert(int distance[], int n) { int minn = 10000000; int index; //индекс следующей вершины for(int i = 0; i < n; i++) { if((!used[i]) && (distance[i] <= minn)) { minn = distance[i]; index = i; } } return index; } void dijkstra(int src, int n) // src - первая вершина { int distance[10]; for(int i = 0; i < n; i++) { distance[i] = 100000000; used[i] = false; } distance[src] = 0; for(int v = 0; v < n; v++) { int u = nextVert(distance, n); // u - следующая вершина used[u] = true; for(auto i : graph[u]) { if(!used[i] && (distance[u] + leng[u][i] < distance[i])) distance[i] = distance[u] + leng[u][i]; } } for(int i = 0; i < n; i++) cout << i+1 << " : " << distance[i] << endl; } int main() { int n, m, x, y, z; cin >> n >> m; for(int i = 0; i < m; i++) { cin >> x >> y >> z; x--; y--; graph[x].push_back(y); graph[y].push_back(x); leng[x][y] = z; leng[y][x] = z; } dijkstra(0, n); }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
edit mode
|
history
|
discussion